Submission #577221

#TimeUsernameProblemLanguageResultExecution timeMemory
577221AngusWongParachute rings (IOI12_rings)C++17
37 / 100
2416 ms215220 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e6+1; int n, cnt[N], dsu[N], sz[N]; vector<int> v[N], v2; set<int> crit, tmp; int vis[N], par[N]; vector<int> cyc; int find(int x){ return dsu[x]==x? x: dsu[x]=find(dsu[x]); } void join(int x, int y){ x=find(x), y=find(y); sz[y]+=sz[x]; dsu[x]=y; } void Init(int N_) { n=N_; for (int i=0; i<n; i++){ cnt[i]=0; dsu[i]=i, sz[i]=1; v[i].clear(); crit.insert(i); vis[i]=0, par[i]=-1; } cyc.clear(); } void setcrit(vector<int> v){ tmp.clear(); for (int i: v){ if (crit.find(i)!=crit.end()) tmp.insert(i); } crit=tmp; } void Link(int A, int B) { cnt[A]=min(cnt[A]+1, 4), cnt[B]=min(cnt[B]+1, 4); v[A].push_back(B); v[B].push_back(A); if (find(A)!=find(B)) join(A, B); else{ // do sth } if (cnt[A]==3){ v2=v[A]; v2.push_back(A); setcrit(v2); }else if (cnt[A]==4) setcrit({A}); if (cnt[B]==3){ v2=v[B]; v2.push_back(B); setcrit(v2); }else if (cnt[B]==4) setcrit({B}); } void dfs(int x, int prev=-1){ vis[x]=1, par[x]=prev; for (int i: v[x]){ if (!vis[i]){ dfs(i, x); continue; } if (i==prev || vis[i]==2) continue; if (!cyc.empty()){ crit.clear(); continue; } int t=x; cyc.push_back(i); while (t!=i){ cyc.push_back(t); t=par[t]; assert(t!=-1); } setcrit(cyc); } vis[x]=2; } int CountCritical() { for (int i=0; i<n; i++){ if (!vis[i]) dfs(i); } return crit.size(); }
#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...