제출 #144513

#제출 시각아이디문제언어결과실행 시간메모리
144513LyestriaSplit the Attractions (IOI19_split)C++14
0 / 100
9 ms6648 KiB
#include "split.h" #include<bits/stdc++.h> using namespace std; const int mn=2e5+10; int p[mn],si[mn]; inline int f(int x){return x==p[x]?x:(p[x]=f(p[x]));} inline int siz(int x){return si[f(x)];} void mrg(int a,int b){a=f(a),b=f(b);if(a==b);else if(si[a]>si[b])si[a]+=si[b],p[b]=a;else si[b]+=si[a],p[a]=b;} void init(){iota(p,p+mn,0);fill(si,si+mn,1);} bool u[mn]; vector<int>g[mn],ans; int s[mn]; int ctr,n; void dfs(int x,int p){ s[x]=1; for(int y:g[x]){ if(y==p)continue; dfs(y,x); s[x]+=s[y]; } } int fc(int x,int p){ for(int y:g[x]){ if(y==p)continue; if(s[y]*2>=n)return fc(y,x); } return x; } void dfs2(int x,int p){ for(int y:g[x]){ if(y==p)continue; dfs2(y,x); mrg(x,y); } } int lef,tar; bool vis[mn]; int conv[4]; void dfs3(int x){ if(!lef)return; vis[x]=1; lef--; ans[x]=conv[tar]; for(int y:g[x]){ if(!vis[y]){ dfs3(y); if(!lef)return; } } } vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { int sm=min(a,min(b,c)),bi=max(a,max(b,c)); if(a==sm)conv[1]=1; else if(a==bi)conv[3]=1; else conv[2]=1; if(b==sm)conv[1]=2; else if(b==bi)conv[3]=2; else conv[2]=2; if(c==sm)conv[1]=3; else if(c==bi)conv[3]=3; else conv[2]=3; b=a+b+c-sm-bi; a=sm; c=bi; n=N; ans.resize(n,conv[3]); int m=p.size(),i; init(); for(i=0;i<m;i++){ if(f(p[i])!=f(q[i])){ mrg(p[i],q[i]); g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); } } dfs(0,-1); ctr=fc(0,-1); init(); for(int y:g[ctr]){ dfs2(y,ctr); if(siz(y)>=a){ vis[ctr]=1; lef=a; tar=1; dfs3(y); lef=b; tar=2; vis[ctr]=0; dfs3(ctr); return ans; } } for(i=0;i<m;i++){ if(p[i]==ctr||q[i]==ctr)continue; if(f(p[i])==f(q[i]))continue; mrg(p[i],q[i]); g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); if(siz(p[i])>=a){ vis[ctr]=1; lef=a; tar=1; dfs3(p[i]); lef=b; tar=2; vis[ctr]=0; dfs3(ctr); return ans; } } fill(ans.begin(),ans.end(),0); 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...