Submission #63420

#TimeUsernameProblemLanguageResultExecution timeMemory
63420zadrgaParachute rings (IOI12_rings)C++14
52 / 100
4029 ms225624 KiB
// 19.44 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1LL << 55) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 1000111 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; struct DSU{ bool over; int n, owner, max_degree, type; set<int> cycles; int deg_comp[maxn][4]; int deg[maxn]; int sz[maxn]; int root[maxn]; int rooting(int x){ if(root[x] == x) return x; return root[x] = rooting(root[x]); } void addEdge(int a, int b){ if(a == owner || b == owner || over == 1) return; int ra = rooting(a); int rb = rooting(b); deg_comp[ra][deg[a]]--; deg[a]++; deg[a] = min(deg[a], 3); deg_comp[ra][deg[a]]++; deg_comp[rb][deg[b]]--; deg[b]++; deg[b] = min(deg[b], 3); deg_comp[rb][deg[b]]++; max_degree = max(max_degree, max(deg[a], deg[b])); if(ra != rb){ root[rb] = ra; sz[ra] += sz[rb]; for(int i = 0; i < 4; i++){ deg_comp[ra][i] += deg_comp[rb][i]; deg_comp[rb][i] = 0; } } if(ra == rb) cycles.insert(ra); if(max_degree == 3 || cycles.size() > 1) over = 1; if(type >= 3 && cycles.size() == 1) over = 1; } void init(int nn, int x, int t, vector<pii> &edge){ n = nn; owner = x; cycles.clear(); max_degree = over = 0; type = t; memset(deg_comp, 0, sizeof(deg)); for(int i = 0; i < maxn; i++){ root[i] = i; deg[i] = 0; sz[i] = 1; } for(pii v : edge) addEdge(v.fi, v.se); } int getAns(){ if(over) return 0; if(type == 2){ if(max_degree <= 1) return n; if(max_degree == 2){ if(cycles.size() == 0) return n; if(cycles.size() == 1) return sz[*cycles.begin()]; } } if(type == 3 || type == 4) return 1; } } dsu[6]; bool start[6]; int deg[maxn], num[5], ind[5], n; vector<pii> edge; vector<int> adj[maxn]; pii cur_range; int all_max_degree; void Init(int N){ n = N; all_max_degree = 0; dsu[0].init(n, -1, 2, edge); memset(ind, -1, sizeof(ind)); memset(deg, 0, sizeof(deg)); num[0] = n; start[0] = 1; cur_range = mp(0, 0); } void Link(int A, int B){ adj[A].pb(B); adj[B].pb(A); num[deg[A]]--; deg[A]++; deg[A] = min(deg[A], 4); num[deg[A]]++; if(ind[deg[A]] == -1) ind[deg[A]] = A; num[deg[B]]--; deg[B]++; deg[B] = min(deg[B], 4); num[deg[B]]++; if(ind[deg[B]] == -1) ind[deg[B]] = B; all_max_degree = max(all_max_degree, max(deg[A], deg[B])); if(all_max_degree == 3){ cur_range = mp(1, 4); if(!start[1]){ start[1] = 1; int cnt = 1; dsu[cnt++].init(n, ind[3], 3, edge); for(int v : adj[ind[3]]) dsu[cnt++].init(n, v, 3, edge); } } if(all_max_degree == 4){ cur_range = mp(5, 5); if(!start[5]){ start[5] = 1; dsu[5].init(n, ind[4], 4, edge); } } // cout << "deg : " << all_max_degree << endl; edge.pb(mp(A, B)); for(int i = cur_range.fi; i <= cur_range.se; i++) dsu[i].addEdge(A, B); } int CountCritical(){ int ret = 0; for(int i = cur_range.fi; i <= cur_range.se; i++) ret += dsu[i].getAns(); return ret; }

Compilation message (stderr)

rings.cpp: In member function 'int DSU::getAns()':
rings.cpp:107:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^
#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...