Submission #49517

#TimeUsernameProblemLanguageResultExecution timeMemory
49517ho94949낙하산 고리들 (IOI12_rings)C++17
100 / 100
1857 ms99708 KiB
#include<vector> #include<algorithm> using namespace std; const int MAXN = 1010101; struct UF { int ufd[MAXN]; int N; UF(){} UF(int n):N(n) { for(int i=0; i<n; ++i) ufd[i] = i; } int Find(int a) { if(a==ufd[a]) return a; return ufd[a] = Find(ufd[a]); } bool Union(int a, int b) { a = Find(a); b = Find(b); if(a==b) return false; ufd[a] = b; return true; } }; struct DAT { UF uf; char deg[MAXN]; int N; int numcyc; int cyclen; bool ovdeg; DAT(){}; DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0){ for(int i=0; i<N; ++i) deg[i] = 0; } void Add(int a, int b) { deg[a]++; deg[b]++; if(deg[a] >= 3 || deg[b] >= 3) ovdeg = 1; if(!uf.Union(a, b)) if((++numcyc) == 1) for(int i=0; i<N; ++i) if(uf.Find(i) == uf.Find(a)) ++cyclen; } }; enum PHASE {DEG2, DEG3_1, DEG3_2, DEG3_3, SP1, INF}; PHASE state; DAT global; int N, M; pair<int, int> EList[MAXN]; vector<int> conn[MAXN]; int deg[MAXN], numdeg[5]; vector<int> specials; vector<DAT> datas; void Init(int _N) { N = _N; M = 0; numdeg[0] = N; DAT d(N); global = d; state = DEG2; } void updatespecials() { for(auto x: specials) { DAT d(N); for(int i=0; i<M; ++i) { if(EList[i].first == x || EList[i].second == x) continue; d.Add(EList[i].first, EList[i].second); } datas.push_back(d); } } void makestate(PHASE state) { specials.clear(); datas.clear(); for(int i=0; i<N; ++i) { int cnt = (deg[i] >= 3)?1:0; for(auto x: conn[i]) if(deg[x] == 3) ++cnt; if(cnt == numdeg[3] + numdeg[4]) specials.push_back(i); } updatespecials(); } void updatestate(PHASE state, int A, int B) { switch(state) { case DEG2: global.Add(A, B); break; default: for(int i=0; i<specials.size(); ++i) { if(specials[i] == A || specials[i] == B) continue; datas[i].Add(A, B); } break; } } void Link(int A, int B) { if(state == INF) return; if(state != DEG2 && datas.size() == 0){state = INF; return;} EList[M++] = make_pair(A, B); numdeg[min(4, deg[A])]--; numdeg[min(4, deg[B])]--; deg[A]++; deg[B]++; numdeg[min(4, deg[A])]++; numdeg[min(4, deg[B])]++; conn[A].push_back(B); conn[B].push_back(A); PHASE newstate = DEG2; if(numdeg[4] >= 2){ state = INF; return;} else if(numdeg[4] == 1 || numdeg[3] >= 4) newstate = SP1; else if(numdeg[3] == 3) newstate = DEG3_3; else if(numdeg[3] == 2) newstate = DEG3_2; else if(numdeg[3] == 1) newstate = DEG3_1; else newstate = DEG2; if(state != newstate) { state = newstate; makestate(state); } else updatestate(state, A, B); } //#include<cstdio> int CountCritical() { //if(state == DEG2) puts("DEG2"); //printf(">%d %d\n", state, (int)datas.size()); int ans = 0; switch(state) { case DEG2: switch(global.numcyc) { case 0: return N; case 1: return global.cyclen; default: return 0; } case INF: return 0; default: for(const auto& x: datas) if(x.numcyc==0 && !x.ovdeg ) ++ans; return ans; } }

Compilation message (stderr)

rings.cpp: In constructor 'DAT::DAT(int)':
rings.cpp:31:32: warning: 'DAT::N' will be initialized after [-Wreorder]
     UF uf; char deg[MAXN]; int N; int numcyc; int cyclen;  bool ovdeg; 
                                ^
rings.cpp:31:8: warning:   'UF DAT::uf' [-Wreorder]
     UF uf; char deg[MAXN]; int N; int numcyc; int cyclen;  bool ovdeg; 
        ^~
rings.cpp:33:5: warning:   when initialized here [-Wreorder]
     DAT(int n): N(n), uf(n), numcyc(0), cyclen(0), ovdeg(0){
     ^~~
rings.cpp: In function 'void updatestate(PHASE, int, int)':
rings.cpp:101:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<specials.size(); ++i)
                          ~^~~~~~~~~~~~~~~~
#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...