Submission #66464

#TimeUsernameProblemLanguageResultExecution timeMemory
66464aquablitz11Parachute rings (IOI12_rings)C++14
37 / 100
1339 ms96436 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int N = 1e6+10; // graph data int n; vector<pii> E, ES; vector<int> G[N]; int dfs(int u, int p, int s, int t) { if (u == t) return 1; for (auto v : G[u]) if (v != p && (u != s || v != t)) { int r = dfs(v, u, s, t); if (r) return r+1; } return 0; } // dsu with copying for experimentation bool ffc = true; int par[N], mfcnt, firstcycle; int root(int u) { if (par[u] == u) return u; return par[u] = root(par[u]); } inline bool merge(int u, int v) { //fprintf(stderr, "merge(%d, %d)\n", u, v); int u0 = u, v0 = v; u = root(u), v = root(v); if (u == v) { if (++mfcnt == 1 && ffc) firstcycle = dfs(u0, -1, u0, v0); return false; } par[u] = v; return true; } int _np[N], _nv[N], tick; inline int &np(int u) { if (_nv[u] != tick) { _np[u] = par[u]; _nv[u] = tick; } return _np[u]; } int nroot(int u) { if (np(u) == u) return u; return np(u) = nroot(np(u)); } inline bool nmerge(int u, int v) { //fprintf(stderr, "nmerge(%d, %d)\n", u, v); u = nroot(u), v = nroot(v); if (u == v) return false; np(u) = v; return true; } // state control (degree freq. histogram) int cntok, cnt3, cnt4; pii mxdeg(0, -1); inline void testmod(int a, int b) { if (a <= 2) --cntok; if (a == 3) --cnt3; if (a >= 4) --cnt4; if (b <= 2) ++cntok; if (b == 3) ++cnt3; if (b >= 4) ++cnt4; } // rebuild dsu with exceptions inline bool must_skip(int u) { if (mxdeg.first < 3) return false; if (u == mxdeg.second) return true; if (mxdeg.first == 3) { for (auto v : G[mxdeg.second]) if (v == u) return true; } return false; } inline void build_dsu() { //fprintf(stderr, "rebuild dsu!\n"); ES.clear(); mfcnt = 0; for (int i = 0; i < n; ++i) par[i] = i; for (auto e : E) { int u = e.first, v = e.second; if (must_skip(u) || must_skip(v)) { ES.emplace_back(u, v); //fprintf(stderr, "skip edge %d %d\n", u, v); continue; } merge(e.first, e.second); } } inline bool modify(int u) { testmod(G[u].size()-1, G[u].size()); if (G[u].size() > mxdeg.first) { mxdeg = pii(G[u].size(), u); if (mxdeg.first == 3 || mxdeg.first == 4) { ffc = false; return true; } } return false; } // testing functions bool dead[N]; inline bool test(int u) { //fprintf(stderr, "test(%d)\n", u); if (dead[u]) return false; testmod(G[u].size(), 0); for (auto v : G[u]) testmod(G[v].size(), G[v].size()-1); bool ok = cnt3 == 0 && cnt4 == 0; ++tick; if (ok) for (auto e : ES) { if (e.first == u || e.second == u) continue; if (!nmerge(e.first, e.second)) ok = false; if (!ok) break; } testmod(0, G[u].size()); for (auto v : G[u]) testmod(G[v].size()-1, G[v].size()); if (!ok) dead[u] = true; return ok; } // problem functions: bool state4 = false; void Init(int n) { //fprintf(stderr, "Init(%d)\n", n); ::n = n; build_dsu(); } void Link(int u, int v) { //fprintf(stderr, "Link(%d, %d)\n", u, v); G[u].push_back(v); G[v].push_back(u); if (state4 && (u == mxdeg.second || v == mxdeg.second)) return; bool m = modify(u) | modify(v); E.emplace_back(u, v); if (m) { build_dsu(); if (mxdeg.first == 4) { state4 = true; testmod(G[mxdeg.second].size(), 0); for (auto a : G[mxdeg.second]) testmod(G[a].size()-1, G[a].size()-1); } } else if (!must_skip(u) && !must_skip(v)) { merge(u, v); } else { ES.emplace_back(u, v); } } int CountCritical() { //fprintf(stderr, "CountCritical()\n"); if (state4) return cnt3 == 0 && cnt4 == 0 && mfcnt == 0; if (mxdeg.first <= 2) { if (mfcnt > 1) return 0; else if (mfcnt == 1) return firstcycle; else if (mfcnt == 0) return n; } if (mfcnt > 0) return 0; int cnt = 0; if (test(mxdeg.second)) ++cnt; if (mxdeg.first == 3) { for (auto v : G[mxdeg.second]) if (test(v)) ++cnt; } return cnt; }

Compilation message (stderr)

rings.cpp: In function 'bool modify(int)':
rings.cpp:110:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (G[u].size() > mxdeg.first) {
         ~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...