Submission #1020219

#TimeUsernameProblemLanguageResultExecution timeMemory
1020219antonParachute rings (IOI12_rings)C++17
0 / 100
3179 ms262144 KiB
#include<bits/stdc++.h> using namespace std; struct DSU{ int nbGroups =0; vector<int> anc; vector<int> sz; vector<pair<int, pair<int, int>>> op_buffer; int nbCycles = 0; int szCycle= 0; DSU(){}; DSU(int l){ anc.resize(l); sz.resize(l); for(int i = 0; i<l; i++){ anc[i] = i; sz[i] = 1; } nbGroups = l; } int c(int u){ op_buffer.push_back({u, {anc[u], sz[u]}}); if(anc[u] == u){ return u; } int v= c(anc[u]); anc[u] =v; return v; } void merge(int a, int b){ //cerr<<"merging "<<a<<" "<<b<<endl; a = c(a); b= c(b); if(a==b){ nbCycles ++; szCycle = sz[a]; return; } nbGroups--; op_buffer.push_back({a, {anc[a], sz[a]}}); op_buffer.push_back({b, {anc[b], sz[b]}}); if(sz[a]>sz[b]){ swap(a, b); } anc[a] = b; sz[b] += sz[a]; } void undo_buffer(){ while(op_buffer.size()>0){ auto e= op_buffer.back(); if(anc[e.first] == e.first){ nbGroups--; } op_buffer.pop_back(); anc[e.first] = e.second.first; sz[e.first] = e.second.second; if(anc[e.first] == e.first){ nbGroups++; } } } }; int N; const int MAX_N= 1e6; vector<int> adj[MAX_N]; unordered_set<int> interesting; bool isInteresting[MAX_N]; int deg[MAX_N], oc[MAX_N]; DSU curDSU; int above3= 0; int above4 = 0; DSU recalcDSU(){ DSU newDSU(N); for(int iV = 0; iV<N; iV++){ for(auto u: adj[iV]){ if(!(isInteresting[u] || isInteresting[iV])){ newDSU.merge(iV, u); } } } newDSU.op_buffer.clear(); return newDSU; } DSU beginDSU; bool lost3 =false; void changeDeg(int u, int d){ if(deg[u]>=3){ above3--; } if(deg[u] >= 4){ above4--; } oc[deg[u]]--; deg[u] +=d; oc[deg[u]] ++; if(deg[u]>=3){ above3++; } if(deg[u] >= 4){ above4++; } } void Init(int N_) { N = N_; fill(&oc[0], &oc[N], 0); fill(&isInteresting[0], &isInteresting[N], true); for(int i = 0; i<N; i++){ interesting.insert(i); } oc[0] =N; curDSU = DSU(N); beginDSU = DSU(N); } bool check_possible(){ return interesting.size()>0; } void updInteresting(int u, bool three){ unordered_set<int> close; if(three){ for(auto e: adj[u]){ close.insert(e); } } close.insert(u); for(auto it = interesting.begin(); it!=interesting.end(); ){ if(close.find(*it) == close.end()){ isInteresting[*it] = false; for(auto ee: adj[*it]){ if(!isInteresting[ee]){ curDSU.merge(*it, ee); } } it = interesting.erase(it); } else{ ++it; } } } bool changed = true; void clear_interesting(){ unordered_set<int> new_interesting; for(auto e: interesting){ if(deg[e] != 4){ isInteresting[e] = false; } else{ new_interesting.insert(e); } } for(auto e: interesting){ for(auto ee: adj[e]){ if(!(isInteresting[ee] ||isInteresting[e])){ curDSU.merge(e, ee); } } } swap(interesting, new_interesting); } void Link(int A, int B) { changed = true; if(above4>1 || lost3){ return; } beginDSU.merge(A, B); adj[A].push_back(B); adj[B].push_back(A); if(deg[A]<4 && deg[B]<4){ changeDeg(A, +1); changeDeg(B, +1); } if((deg[A]== 3 || deg[B]==3)){ if(deg[A] != 3){ swap(A, B); } updInteresting(A, true); if(deg[B] == 3){ updInteresting(B, true); } if(above4 == 0){ curDSU = recalcDSU(); } } if(isInteresting[A] || isInteresting[B]){ } else{ curDSU.merge(A, B); curDSU.op_buffer.clear(); } if((deg[A] == 4 || deg[B]== 4) && above4 == 1){ if(deg[A] != 4){ swap(A, B); } updInteresting(A, false); for(int i = 0; i<N; i++){ if(deg[i] != 4){ for(auto e: adj[i]){ if(deg[e] == 4){ oc[deg[i]]--; deg[i]--; oc[deg[i]]++; } } } } if(deg[B] == 4){ updInteresting(B, false); } } lost3 = !check_possible(); } int prev_res= 0; int calc(){ if(above4>1 || lost3){ return 0; } else{ if(above4 == 1){ if((oc[0])*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==1){ return 1; } return 0; } else if(above3>=1){ int res= 0; for(auto iAdd: interesting){ for(auto e: adj[iAdd]){ if(!isInteresting[e]){ changeDeg(e, -1); } changeDeg(iAdd, -1); } } curDSU.op_buffer.clear(); for(auto iRem: interesting){ if(deg[iRem]>=4 || above4 ==0){ for(auto iAdd: interesting){ if(iAdd!=iRem){ for(auto e: adj[iAdd]){ if(e!=iRem){ curDSU.merge(e, iAdd); if(!isInteresting[e]){ changeDeg(e, 1); } changeDeg(iAdd, 1); } } } } if((oc[0]-1)*2 + oc[1] == (curDSU.nbGroups-1)*2 && above3 ==0){ res++; } for(auto iAdd: interesting){ if(iAdd!=iRem){ for(auto e: adj[iAdd]){ if(e!=iRem){ if(!isInteresting[e]){ changeDeg(e, -1); } changeDeg(iAdd, -1); } } } } curDSU.undo_buffer(); } } for(auto iAdd: interesting){ for(auto e: adj[iAdd]){ if(!isInteresting[e]){ changeDeg(e, 1); } changeDeg(iAdd, 1); } } return res; } else{ if(beginDSU.nbCycles == 0){ return N; } else if(beginDSU.nbCycles == 1){ return beginDSU.szCycle; } else{ return 0; } } } } int CountCritical() { if(!changed){ return prev_res; } prev_res = calc(); return prev_res; }
#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...