Submission #426279

#TimeUsernameProblemLanguageResultExecution timeMemory
426279wiwihoParachute rings (IOI12_rings)C++14
100 / 100
2752 ms154520 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream& operator<<(ostream& o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } ll ifloor(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a < 0) return (a - b + 1) / b; else return a / b; } ll iceil(ll a, ll b){ if(b < 0) a *= -1, b *= -1; if(a > 0) return (a + b - 1) / b; else return a / b; } int n = -1; vector<pii> edge; vector<vector<int>> g; struct DSU{ vector<int> dsu; vector<int> deg, cnt, one, sz; int cycle = -1; int con = 0; void init(){ con = n; cnt.resize(4); dsu.resize(n); deg.resize(n); one.resize(n); sz.resize(n, 1); cnt[0] = n; for(int i = 0; i < n; i++) dsu[i] = i; } int findDSU(int a){ if(dsu[a] != a) dsu[a] = findDSU(dsu[a]); return dsu[a]; } void unionDSU(int a, int b){ int pa = findDSU(a); int pb = findDSU(b); if(deg[a] == 1) one[pa]--; if(deg[b] == 1) one[pb]--; cnt[min(deg[a], 3)]--; cnt[min(deg[b], 3)]--; if(pa != pb){ dsu[pb] = pa; con--; one[pa] += one[pb]; sz[pa] += sz[pb]; } deg[a]++; deg[b]++; if(deg[a] == 1) one[pa]++; if(deg[b] == 1) one[pa]++; cnt[min(deg[a], 3)]++; cnt[min(deg[b], 3)]++; if(sz[pa] > 1 && one[pa] == 0) cycle = sz[pa]; } bool ok(){ return cnt[3] == 0 && cnt[1] == (con - cnt[0]) * 2; } int cy(){ if(cnt[3] != 0 || cnt[1] + 2 != (con - cnt[0]) * 2) return -1; return cycle; } void print(){ cerr << "DSU " << ok() << " " << cy() << " " << con << "\n"; cerr << "dsu: "; printv(dsu, cerr); cerr << "sz: "; printv(sz, cerr); cerr << "cnt: "; printv(cnt, cerr); cerr << "deg: "; printv(deg, cerr); } }; struct OAO{ int no; DSU dsu; explicit OAO(int no = -1): no(no) { if(n != -1) dsu.init(); for(pii p : edge){ addedge(p.F, p.S); } } void addedge(int u, int v){ if(u == no || v == no) return; dsu.unionDSU(u, v); } }; OAO all; vector<OAO> oao; int status = 0; void neighbor(int v){ if(status >= 1) return; status = 1; oao.clear(); oao.eb(OAO(v)); for(int i : g[v]) oao.eb(OAO(i)); } void only(int v){ if(status >= 2) return; status = 2; oao.clear(); oao.eb(OAO(v)); } void addedge(int u, int v){ g[u].eb(v); g[v].eb(u); edge.eb(mp(u, v)); all.addedge(u, v); for(OAO& oao : oao) oao.addedge(u, v); if(g[u].size() == 3) neighbor(u); if(g[u].size() == 4) only(u); if(g[v].size() == 3) neighbor(v); if(g[v].size() == 4) only(v); } void Init(int N){ n = N; all.dsu.init(); g.resize(n); } void Link(int u, int v){ addedge(u, v); } int CountCritical(){ // cerr << "test\n"; // all.dsu.print(); // for(OAO& t : oao){ // cerr << "test " << t.no << "\n"; // t.dsu.print(); // } if(all.dsu.ok()) return n; else if(all.dsu.cy() != -1) return all.dsu.cy(); int ans = 0; for(OAO& t : oao) ans += t.dsu.ok(); return ans; }
#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...