제출 #65789

#제출 시각아이디문제언어결과실행 시간메모리
65789aquablitz11낙하산 고리들 (IOI12_rings)C++14
20 / 100
4106 ms157292 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int N = 1e6+10; int n; set<int> G[N]; vector<pii> E; // maintaining list of test nodes int c02; set<int> d3, d4; inline void movenode(int u, int a, int b) { if (a <= 2) --c02; if (a == 3) d3.erase(u); if (a >= 4) d4.erase(u); if (b <= 2) ++c02; if (b == 3) d3.insert(u); if (b >= 4) d4.insert(u); } inline set<int> testnodes() { if (d3.size() == 0 && d4.size() == 0) return set<int>(); if (d4.size() > 0) return d4; set<int> ans = d3; for (auto u : d3) { for (auto v : G[u]) ans.insert(v); } return ans; } inline bool cancut(int u) { if (d4.size() > 0) return d4.count(u); if (d3.size() > 0) return d3.count(u); return false; } // disjoint set int par[N]; bool mergefail = false; int root(int u) { if (par[u] == u) return u; return par[u] = root(par[u]); } inline void merge(int u, int v) { u = root(u), v = root(v); if (u == v) mergefail = true; else par[u] = v; } /*inline void builddsu() { mergefail = false; for (int u = 0; u < n; ++u) par[u] = u; for (auto e : E) { int u = e.first, v = e.second; if (!cancut(u) && !cancut(v)) merge(u, v); } } 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 newroot(int u) { if (np(u) == u) return u; return np(u) = newroot(np(u)); } inline bool newmerge(int u, int v) { u = newroot(u), v = newroot(v); if (u == v) return false; np(u) = v; return true; }*/ // testing system: bool checkcycle(int x) { mergefail = false; for (int u = 0; u < n; ++u) par[u] = u; for (auto e : E) { int u = e.first, v = e.second; if (u == x || v == x) continue; merge(u, v); if (mergefail) return false; } return true; } bool dead[N]; bool test(int u) { if (dead[u]) return false; movenode(u, G[u].size(), 0); for (auto v : G[u]) movenode(v, G[v].size(), G[v].size()-1); //++tick; bool ans = d3.size() == 0 && d4.size() == 0 && checkcycle(u); movenode(u, 0, G[u].size()); for (auto v : G[u]) movenode(v, G[v].size()-1, G[v].size()); if (!ans) dead[u] = true; return ans; } // problems: void Init(int n) { ::n = n; } void Link(int a, int b) { E.emplace_back(a, b); movenode(a, G[a].size(), G[a].size()+1); movenode(b, G[b].size(), G[b].size()+1); G[a].insert(b); G[b].insert(a); } int mnans = 1e9; int CountCritical() { if (mnans == 0 || d4.size() > 1 || d3.size() > 4) return mnans = 0; if (d3.size() == 0 && d4.size() == 0 && checkcycle(-1)) return mnans = n; int cnt = 0; for (int u = 0; u < n; ++u) if (test(u)) ++cnt; return mnans = cnt; }
#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...