Submission #36807

#TimeUsernameProblemLanguageResultExecution timeMemory
36807mohammad_kilaniParachute rings (IOI12_rings)C++14
100 / 100
2332 ms113148 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int n , comp[N], mx , adj[N] , ans = 0 , cycles = 0 , vis[N] , vi = 0 , comp2[4][N] , con1[4][N] , con2[4][N]; vector< int > g[N]; vector< pair<int,bool> > v; vector< pair<int,int> > v2; int Find(int u){ return (u == comp[u] ? u : comp[u] = Find(comp[u])); } int Find2(int u,int i){ if(u == comp2[i][u]) return u; return comp2[i][u] = Find2(comp2[i][u],i); } void Init(int N_) { n = N_; ans = n ; for(int i=0;i<n;i++) comp[i] = i; mx = 0 ; cycles = 0 ; } void DFS(int node,int prnt,int last){ ans++; if(node == last) return; for(int i=0;i<(int)g[node].size();i++){ if(g[node][i] != prnt) DFS(g[node][i],node,last); } } void DFS2(int node,int cant){ vis[node] = vi; int num = 0 ; for(int i=0;i<(int)g[node].size();i++){ int newnode = g[node][i]; num += (newnode != cant); if(vis[newnode] == vi || newnode == cant) continue; DFS2(newnode,cant); } v2.push_back(make_pair(node,num)); } void make(int u){ v.push_back(make_pair(u,true)); for(int i=0;i<(int)g[u].size();i++){ v.push_back(make_pair(g[u][i],true)); } ans = 0 ; for(int i=0;i<(int)v.size();i++){ vi++; int cnt = 0 ; for(int j=0;j<n;j++){ if(j == v[i].first || vis[j] == vi) continue; v2.clear(); cnt = j; DFS2(j,v[i].first); if(v2.size() == 1){ con1[i][cnt] = con2[i][cnt] = v2[0].first; comp2[i][v2[0].first] = cnt; } else if(v2.size() == 2){ con1[i][cnt] = v2[0].first; con2[i][cnt] = v2[1].first; comp2[i][v2[0].first] = comp2[i][v2[1].first] = cnt; } else{ con1[i][cnt] = con2[i][cnt] = -1; for(int k=0;k<(int)v2.size();k++){ if(v2[k].second == 1) if(con1[i][cnt] == -1) con1[i][cnt] = v2[k].first; else con2[i][cnt] = v2[k].first; comp2[i][v2[k].first] = cnt; } if(con1[i][cnt] == -1){ v[i].second = false; break; } } } ans += v[i].second; } } void Link(int a, int b) { if(ans == 0) return; if(mx < 3){ int u = Find(a); int v = Find(b); adj[a]++; adj[b]++; g[a].push_back(b); g[b].push_back(a); if(adj[a] == 3){ mx = 3; make(a); return ; } if(adj[b] == 3){ mx = 3; make(b); return; } if(u == v){ if(cycles > 0){ ans = 0; return ; } cycles++; ans = 0 ; DFS(a,b,b); } else{ comp[u] = v; } return ; } for(int i=0;i<(int)v.size();i++){ if(v[i].second == false) continue; if(a == v[i].first || b == v[i].first){ adj[v[i].first]++; if(adj[v[i].first] > 3 && v.size() > 1){ int cur = v[i].first; ans = 1; v.clear(); v.push_back(make_pair(cur,1)); break; } continue; } int u = Find2(comp2[i][a],i); int vv = Find2(comp2[i][b],i); if(u == vv){ v[i].second = false; ans--; continue; } if(a != con1[i][u] && a != con2[i][u]){ v[i].second = false; ans--; continue; } if(b != con1[i][vv] && b != con2[i][vv]){ v[i].second = false; ans--; continue; } comp2[i][u] = vv; if(a == con1[i][u] && b == con1[i][vv]){ con1[i][vv] = con2[i][u]; } else if(a == con2[i][u] && b == con1[i][vv]){ con1[i][vv] = con1[i][u]; } else if(a == con1[i][u] && b == con2[i][vv]){ con2[i][vv] = con2[i][u]; } else if(a == con2[i][u] && b == con2[i][vv]){ con2[i][vv] = con1[i][u]; } } } int CountCritical() { return ans; }

Compilation message (stderr)

rings.cpp: In function 'void make(int)':
rings.cpp:75:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
      if(v2[k].second == 1) if(con1[i][cnt] == -1) con1[i][cnt] = v2[k].first; else con2[i][cnt] = v2[k].first;
        ^
#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...