Submission #789851

#TimeUsernameProblemLanguageResultExecution timeMemory
789851PoonYaPatParachute rings (IOI12_rings)C++14
37 / 100
2929 ms199484 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int n,p[1000005],r[1000005],lst=-1,deg[1000005]; vector<int> adj[1000005],br; vector<pii> edge; set<int> ans; bool nope=false; vector<int> st; void dfs(int x, int par, int tar) { st.push_back(x); if (x==tar && par!=-1) { for (auto s : st) br.push_back(s); br.pop_back(); } else { for (auto s : adj[x]) { if (s==par) continue; if (s==tar && par==-1) continue; dfs(s,x,tar); } } st.pop_back(); } int find(int x) { while (x!=p[x]) x=p[x]; return x; } void unite(int a, int b) { a=find(a); b=find(b); if (r[a]<r[b]) swap(a,b); p[b]=a; if (r[a]==r[b]) ++r[a]; } void Init(int N_) { n=N_; for (int i=0; i<n; ++i) ans.insert(i), p[i]=i; } void add(vector<int> x) { set<int> temp; for (auto s : x) if (ans.find(s)!=ans.end()) temp.insert(s); swap(temp,ans); } void Link(int A, int B) { if (nope) return; if (lst==-1) { adj[A].push_back(B); adj[B].push_back(A); edge.push_back(pii(A,B)); if (adj[A].size()==3) add({adj[A][0],adj[A][1],adj[A][2],A}); else if (adj[A].size()==4) for (auto s : adj[A]) if (ans.find(s)!=ans.end()) ans.erase(ans.find(s)); if (adj[B].size()==3) add({adj[B][0],adj[B][1],adj[B][2],B}); else if (adj[B].size()==4) for (auto s : adj[B]) if (ans.find(s)!=ans.end()) ans.erase(ans.find(s)); if (find(A)==find(B)) { br.clear(); dfs(A,-1,A); add(br); } else unite(A,B); if (ans.size()==0) nope=true; if (ans.size()==1) { lst=*(ans.begin()); for (int i=0; i<n; ++i) p[i]=i; for (auto s : edge) { if (s.first!=lst && s.second!=lst) { ++deg[s.first]; ++deg[s.second]; unite(s.first,s.second); } } } } else { if (A!=lst && B!=lst) { ++deg[A]; ++deg[B]; if (deg[A]>2 || deg[B]>2 || find(A)==find(B)) nope=true; unite(A,B); } } } int CountCritical() { if (nope) return 0; return ans.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...