Submission #374285

---

Source Code Expand

#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif
 
#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()
 
std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }
 
#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }
 
 
 
 
 
class MaximumIndependentSet
{
public:
  MaximumIndependentSet(int n);
  void addEdge(int a, int b);
  void recur(int pos, int mask_num, std::vector<int> &mask);
  std::vector<int> getMaximumIndependentSet();
private:
  int n;
  std::vector<std::vector<int>> relatives;
  std::vector<std::vector<int>> edges;
  int best_mask_num;
  std::vector<int> best_mask;
};
 
inline void MaximumIndependentSet::recur(int pos, int mask_num, std::vector<int> &mask)
{
  if((n - pos) + mask_num <= best_mask_num) return;
  if(pos == n){
    best_mask_num = mask_num;
    best_mask = mask;
    return;
  }
  for(int relative: relatives[pos]){
    if(mask[relative]) continue;
    bool ok = false;
    for(auto adj: edges[relative])if(mask[adj]) ok = true;
    if(!ok) return;
  }
 
  int not_selected_cnt = 0;
  int selected_cnt = 0;
  for(int adj: edges[pos]){
    if(adj < pos){
      if(mask[adj]) selected_cnt += 1;
      else not_selected_cnt += 1;
    }
  }
  if(selected_cnt == 0){
    mask[pos] = 1;
    recur(pos + 1, mask_num + 1, mask);
  }
  if(not_selected_cnt != edges[pos].size()){
    mask[pos] = 0;
    recur(pos + 1, mask_num + 0, mask);
  }
}
 
std::vector<int> MaximumIndependentSet::getMaximumIndependentSet()
{
  relatives = vector<vector<int>>(n + 1);
  for(int pos = 0; pos < n; ++pos){
    int maxi = pos;
    for(int adj: edges[pos]) maxi = max(maxi, adj);
    relatives[maxi + 1].push_back(pos);
  }
  std::vector<int> mask(n, 0);
  best_mask_num = 0;
  best_mask = std::vector<int>(n, 0);
  recur(0, 0, mask);
  
  vector<int> res;
  for(int i = 0; i < n; ++i)if(best_mask[i]) res.push_back(i);
  return res;
}
 
 
MaximumIndependentSet::MaximumIndependentSet(int n)
{
  this->n = n;
  edges.resize(n);
}
 
void MaximumIndependentSet::addEdge(int a, int b)
{
  assert(0 <= a && a < n);
  assert(0 <= b && b < n);
  assert(a != b);
 
  edges[a].push_back(b);
  edges[b].push_back(a);
}
 

/*
  
tuple<i64, i64> calc(i64 mask, i64 independent_set, vector<int> &independents, vector<tuple<int, int>> &edges_0, vector<tuple<int, int>> &edges_1)
{
  const i64 MAX = 50;
  int minus_cnt[MAX];
  int plus_cnt[MAX];
  for(auto t: independents){
    minus_cnt[t] = 0;
    plus_cnt[t] = 0;
  }
  i64 cnt = 0;
  //DEBUG(mask, independent_set);
  for(auto edge: edges_0){
    int i_0 = get<0>(edge);
    int i_1 = get<1>(edge);
    //DEBUG(i_0, i_1);
    
    if(independent_set & bit(i_0)){
      if(mask & bit(i_1)) plus_cnt[i_0] += 1;
      else minus_cnt[i_0] += 1;
      continue;
    }else{
      if(mask & bit(i_0)) plus_cnt[i_1] += 1;
      else minus_cnt[i_1] += 1;
      continue;
    }
  }
  for(auto edge: edges_1){
    int i_0 = get<0>(edge);
    int i_1 = get<1>(edge);
    if(((mask & bit(i_0)) == 0) ^ ((mask & bit(i_1)) == 0)) ++cnt;
  }
  i64 way = 1;
  for(auto t: independents){
    cnt += max(minus_cnt[t], plus_cnt[t]);
    if(minus_cnt[t] == plus_cnt[t]) way *= 2;
  }
  //DEBUG(cnt, way);
  return make_tuple(cnt, way);
}


*/


const i64 MAX = 50;
i64 best_score;
i64 best_way;
i64 cur_score;
i64 n = 0;
vector<i64> global_edges[MAX];
int minus_cnt[MAX];
int plus_cnt[MAX];
int colors[MAX];
void recur(i64 pos, i64 independent_mask, vector<int> &independent_set)
{
  if(pos == n){
    i64 score = cur_score;
    i64 way = 1;
    for(auto t: independent_set){
      score += max(minus_cnt[t], plus_cnt[t]);
      if(minus_cnt[t] == plus_cnt[t]) way *= 2;
    }
    //DEBUG(pos, independent_mask, independent_set);
    //DEBUG(score, way);
    if(best_score <= score){
      if(best_score < score) best_way = 0;
      best_score = score;
      best_way += way;
    }
    return;
  }
  if(independent_mask & bit(pos)){
    recur(pos + 1, independent_mask, independent_set);
  }else{
    rep(color, 2){
      colors[pos] = color;
      for(auto adj: global_edges[pos]){
        if(independent_mask & bit(adj)){
          if(color == 0) minus_cnt[adj] += 1;
          else plus_cnt[adj] += 1;
        }else if(adj < pos){
          if(colors[pos] != colors[adj]) cur_score += 1;
        }
      }
      recur(pos + 1, independent_mask, independent_set);
      for(auto adj: global_edges[pos]){
        if(independent_mask & bit(adj)){
          if(color == 0) minus_cnt[adj] -= 1;
          else plus_cnt[adj] -= 1;
        }else if(adj < pos){
          if(colors[pos] != colors[adj]) cur_score -= 1;
        }
      }      
    }
  }
}
 
int main()
{
  unordered_map<char, i64> mp;
  string s;
  cin >> s;
 
  i64 ans = 0;
  vector<tuple<i64, i64>> edges;
  for(i64 pos = 0; pos < sz(s); pos += 4){
    if(mp.count(s[pos + 0]) == 0) mp[s[pos + 0]] = n++;
    if(mp.count(s[pos + 2]) == 0) mp[s[pos + 2]] = n++;
    if(s[pos + 0] == s[pos + 2]) continue;
    edges.push_back(make_tuple(mp[s[pos + 0]], mp[s[pos + 2]]));
  }
  MaximumIndependentSet obj(n);
  for(tuple<i64, i64> tup: edges){
    if(get<0>(tup) == get<1>(tup)) continue;
    global_edges[get<0>(tup)].push_back(get<1>(tup));
    global_edges[get<1>(tup)].push_back(get<0>(tup));
    obj.addEdge(get<0>(tup), get<1>(tup));
  }
  //DEBUG(mp);
  //DEBUG(edges);
  vector<int> independent_set = obj.getMaximumIndependentSet();
  //DEBUG(independent_set);
  i64 independent_mask = 0;
  for(auto t: independent_set) independent_mask |= bit(t);
  /*
 
  i64 not_independent_mask = bit(n) - 1;
  set<i64> independent_set_s;
  for(auto t: independent_set) independent_set_s.insert(t);
  for(auto t: independent_set) not_independent_mask ^= bit(t);


  vector<tuple<int, int>> edges_0;
  vector<tuple<int, int>> edges_1;
  for(auto edge: edges){
    int i_0 = get<0>(edge);
    int i_1 = get<1>(edge);
    //DEBUG(i_0, i_1);
    
    if(((bit(n) - 1) ^ not_independent_mask) & bit(i_0)){
      edges_0.push_back(edge);
      continue;
    }
    if(((bit(n) - 1) ^ not_independent_mask) & bit(i_1)){
      edges_0.push_back(edge);
      continue;
    }
    edges_1.push_back(edge);
  }

  */
  /*
  i64 best = 0;
  i64 way = 0;
  for(i64 mask = not_independent_mask; true;){
    tuple<i64, i64> tup = calc(mask, (bit(n) - 1) ^ not_independent_mask, independent_set, edges_0, edges_1);
    if(best <= get<0>(tup)){
      if(best < get<0>(tup)){
        best = get<0>(tup);
        way = 0;
      }
      way += get<1>(tup);
    }
    if(mask == 0) break;
    mask = (mask - 1) & not_independent_mask;
  }
  */
  recur(0, independent_mask, independent_set);
  cout << best_way << endl;
}
 
 
 
 

Submission Info

Judge Result