Submission #821627

#TimeUsernameProblemLanguageResultExecution timeMemory
821627BaytoroSplit the Attractions (IOI19_split)C++17
18 / 100
475 ms1048576 KiB
#include "split.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; const int maxN=1e5+5; vector<int> ans,g[maxN]; int used[maxN]; void dfs(int x, int &d, int c){ if(d<=0) return; ans[x]=c; used[x]=1; for(auto it: g[x]){ if(used[it]) continue; dfs(it,--d,c); } } int sz[maxN],p[maxN]; int N; int A,B,C; int u=-1,v=-1,s=-1,h=-1; int x,y; void DFS(int x, int par){ p[x]=par; sz[x]=1; for(auto it: g[x]){ if(it==par) continue; DFS(it,x); sz[x]+=sz[it]; } } void col(int x, int c){ ans[x]=c; for(auto it: g[x]){ if(p[x]==it) continue; col(it,c); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { N=n;int m=p.size(); ans.resize(n); A=a,B=b,C=c; if(A>B) swap(A,B); if(B>C) swap(B,C); if(A>B) swap(A,B); bool ok=1,sb1=1; for(int i=0;i<m;i++){ g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); if(g[p[i]].size()>2) sb1=0; if(g[q[i]].size()>2) sb1=0; } if(sb1){ for(int i=0;i<n;i++){ if(g[i].size()==1 && ok){ dfs(i,b,2); ok=0; } else if(g[i].size()==1 && !ok){ dfs(i,a,1); break; } } if(ok){ dfs(0,b,2); for(int i=0;i<n;i++){ if(!used[i]){ dfs(i,a,1); break; } } } for(int i=0;i<n;i++){ if(!ans[i]) ans[i]=3; } return ans; } else if(a==1){ dfs(0,b,2); bool ok=0; for(int i=0;i<n;i++){ if(ans[i]) continue; ans[i]=3; if(!ok) ans[i]=1; ok=1; } return ans; } else{ DFS(0,0); for(int i=0;i<n;i++){ if(sz[i]>=a && n-sz[i]>=b){ col(i,1); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=2; } return ans; } if(sz[i]>=a && n-sz[i]>=c){ col(i,1); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=3; } return ans; } if(sz[i]>=b && n-sz[i]>=a){ col(i,2); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=1; } return ans; } if(sz[i]>=b && n-sz[i]>=c){ col(i,2); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=3; } return ans; } if(sz[i]>=c && n-sz[i]>=a){ col(i,3); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=1; } return ans; } if(sz[i]>=c && n-sz[i]>=b){ col(i,3); for(int j=0;j<n;j++){ if(!ans[j]) ans[j]=2; } return ans; } } return ans; } }
#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...