Submission #588137

#	Time	Username	Problem	Language	Result	Execution time	Memory
588137		MilosMilutinovic	Logičari (COCI21_logicari)	C++14	110 / 110	599 ms	205888 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 02.07.2022 11:58:28
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define int long long

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> f(n);
  vector<int> par(n);
  vector<int> cyc;
  function<void(int, int)> Dfs = [&](int v, int pr) {
    if (!cyc.empty()) {
      return;
    }
    f[v] = 1;
    par[v] = pr;
    for (int u : g[v]) {
      if (u != pr && f[u] == 1) {
        int x = v;        
        while (x != u) {    
          cyc.push_back(x);
          x = par[x];
        }
        cyc.push_back(u);
        return;
      }     
      if (u != pr && f[u] == 0) {
        Dfs(u, v);
        if (!cyc.empty()) {
          return;
        }
      }
    }
    f[v] = 2;
  };
  Dfs(0, 0);
  reverse(cyc.begin(), cyc.end());
  vector<bool> on(n);
  for (int i = 0; i < (int) cyc.size(); i++) {
    on[cyc[i]] = true;
  }
  const long long inf = 1e7;                                       
  vector<vector<vector<long long>>> dp(n, vector<vector<long long>>(2, vector<long long>(2, inf)));
  function<void(int, int)> Solve = [&](int v, int pr) {
    vector<int> ch;
    for (int u : g[v]) {
      if (u == pr || on[u]) {
        continue;
      }
      Solve(u, v);
      ch.push_back(u);
    }
    if (ch.empty()) {
      dp[v][0][0] = 0;
      dp[v][1][0] = 1;
      return;
    }
    {
      // color v
      long long ft = 0;
      for (int i : ch) {
        ft += dp[i][0][0];
      }
      dp[v][1][0] = min(inf, ft + 1);
      for (int i : ch) {
        dp[v][1][1] = min(dp[v][1][1], ft - dp[i][0][0] + dp[i][1][0] + 1);  
      }
    }
    {
      // don't color v 
      long long ft = 0;
      for (int i : ch) { 
        ft += dp[i][0][1];
      }
      dp[v][0][0] = min(inf, ft);
      for (int i : ch) {
        dp[v][0][1] = min(dp[v][0][1], ft - dp[i][0][1] + dp[i][1][1]);
      }       
    }
  };
  for (int i = 0; i < n; i++) {
    if (!on[i]) {
      continue;
    }
    Solve(i, i);
  }                                     
  int m = (int) cyc.size();
  vector<vector<vector<long long>>> pref(m, vector<vector<long long>>(8, vector<long long>(8, inf)));
  vector<vector<vector<long long>>> suff(m, vector<vector<long long>>(8, vector<long long>(8, inf)));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        if (j == 1 && k == 1) {
          continue;
        }
        int state = i * 4 + j * 2 + k;
        pref[0][state][state] = dp[cyc[0]][i][j];   
        suff[m - 1][state][state] = dp[cyc[m - 1]][i][j];
      }    
    }
  }
  for (int i = 0; i < (int) cyc.size(); i++) {
    debug(cyc[i], dp[cyc[i]]);
  }   
  for (int i = 1; i < m; i++) {
    for (int x = 0; x < 8; x++) {
      for (int prv = 0; prv < 8; prv++) {
        for (int st = 0; st < 8; st++) {
          if ((st & 1) != (prv >> 2 & 1)) {
            continue;
          }
          if ((st & 1) && (st >> 1 & 1)) {
            continue;
          } 
          int cx = 0;
          if (st >> 2 & 1) {
            cx += 1;
          }
          if (prv & 1) {
            cx += 1;
          }
          if (prv >> 1 & 1) {
            cx += 1;
          }
          if (cx != 1) {
            continue;
          }
          pref[i][x][st] = min(pref[i][x][st], pref[i - 1][x][prv] + dp[cyc[i]][st >> 2 & 1][st >> 1 & 1]);
        }
      }
    }
  }
  debug(pref[1][5][1]);
  debug(suff[2][5][5]); 
  // todo: Dfs dp and merge of (xx, yy) 
  for (int i = m - 2; i >= 0; i--) {
    for (int x = 0; x < 8; x++) {
      for (int prv = 0; prv < 8; prv++) {
        for (int st = 0; st < 8; st++) {
          if ((st & 1) != (prv >> 2 & 1)) {
            continue;
          }
          if ((st & 1) && (st >> 1 & 1)) {
            continue;
          } 
          int cx = 0;
          if (st >> 2 & 1) {
            cx += 1;
          }
          if (prv & 1) {
            cx += 1;
          }
          if (prv >> 1 & 1) {
            cx += 1;
          }
          if (cx != 1) {
            continue;
          }
          suff[i][x][st] = min(suff[i][x][st], suff[i + 1][x][prv] + dp[cyc[i]][st >> 2 & 1][st >> 1 & 1]);
        }
      }
    }
  }
  long long ans = inf;
  for (int i = 0; i < 8; i++) {
    if (i < 4) {
      continue;
    }
    for (int j = 0; j < 8; j++) {
      int cx = 0;
      if (j & 1) {
        cx += 1;
      }
      if (j >> 1 & 1) {
        cx += 1;
      }
      if (i & 1) {
        cx += 1;
      }
      if (cx != 1) {
        continue;        
      }
      if (j < 4) {
        continue;
      }
      //ans = min(ans, pref[m - 1][i][j]);
    }
  }
  for (int i = 0; i < m - 1; i++) {
    for (int x = 0; x < 8; x++) {
      for (int y = 0; y < 8; y++) {
        if ((x & 1) != (y >> 2 & 1)) {
          continue;
        }  
        if ((y & 1) != (x >> 2 & 1)) {
          continue;
        }    
        for (int xx = 0; xx < 8; xx++) {
          for (int yy = 0; yy < 8; yy++) {
            {
              int cx = (yy >= 4);
              if (xx & 1) {
                cx += 1;
              }
              if (xx >> 1 & 1) {
                cx += 1;
              }
              if (cx != 1) { 
                continue;
              }
            }
            {
              int cx = (xx >= 4);
              if (yy & 1) {
                cx += 1;
              }
              if (yy >> 1 & 1) {
                cx += 1;
              }
              if (cx != 1) { 
                continue;
              }
            }
            if (pref[i][x][xx] + suff[i + 1][y][yy] == 3) {
              debug(i, x, xx, y, yy);
            }
            ans = min(ans, pref[i][x][xx] + suff[i + 1][y][yy]);    
          }
        }
      }
    } 
  }
  cout << (ans >= inf ? -1 : ans) << '\n';
  return 0;
}                                    

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:158:5: note: in expansion of macro 'debug'
  158 |     debug(cyc[i], dp[cyc[i]]);
      |     ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:188:3: note: in expansion of macro 'debug'
  188 |   debug(pref[1][5][1]);
      |   ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:189:3: note: in expansion of macro 'debug'
  189 |   debug(suff[2][5][5]);
      |   ^~~~~
Main.cpp:45:20: warning: statement has no effect [-Wunused-value]
   45 | #define debug(...) 42
      |                    ^~
Main.cpp:280:15: note: in expansion of macro 'debug'
  280 |               debug(i, x, xx, y, yy);
      |               ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 40 / 40
• Subtask 4: 50 / 50