제출 #297713

#제출 시각아이디문제언어결과실행 시간메모리
297713amiratouSplit the Attractions (IOI19_split)C++14
0 / 100
625 ms1048580 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)(x.size()) const int MX = (int)(1e5+5); vector<int> vec[MX],res; int s[MX],A,B,C,c_a,c_b,c_c,cnt; void dfs(int node,int p){ s[node]=1; for(auto it:vec[node]) if(it!=p)dfs(it,node),s[node]+=s[it]; } bool comp(int a,int b){ if(s[a]!=s[b])return s[a]>s[b]; return a<b; } int solve(int node,int p){ //cerr<<node<<" , "; //cerr<<sz(vec[node])<<"\n"; vector<int> g; for(auto it:vec[node]) if(it!=p)g.push_back(it); sort(g.begin(),g.end(),comp); if(A==1 && sz(g)>=1 && s[g[0]]>=B)return node; if(sz(g)>=2){ if(s[g[0]]>=B && (s[g[1]]+1)>=A) return node; return solve(g[0],node); } if(sz(g)>=1)return solve(g[0],node); return -1; } void gimme(int node,int p,int o=0){ if(!cnt)return; cnt--; //cerr<<node<<" "<<o<<"\n"; if(!o)res[node]=c_a; else res[node]=c_b; for(auto it:vec[node]) if(it!=p)gimme(it,node,o); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { res.resize(n); fill(res.begin(),res.end(),0); for (int i = 0; i < n-1; ++i) { vec[p[i]].push_back(q[i]); vec[q[i]].push_back(p[i]); } dfs(0,0); c_a=1,c_b=2,c_c=3; if(a>b)swap(a,b),swap(c_a,c_b); if(a>c)swap(a,c),swap(c_a,c_c); if(b>c)swap(b,c),swap(c_b,c_c); /*cerr<<a<<" "<<b<<" "<<c<<"\n"; cerr<<c_a<<" "<<c_b<<" "<<c_c<<"\n";*/ A=a,B=b,C=c; int idx=solve(0,0); if(idx==-1) return res; //cerr<<idx<<"\n"; res[idx]=c_a; dfs(idx,idx); sort(vec[idx].begin(),vec[idx].end(),comp); if(a!=1)cnt=a-1,gimme(vec[idx][1],idx); cnt=b,gimme(vec[idx][0],idx,1); for (int i = 0; i < n; ++i) if(!res[i])res[i]=c_c; return res; }
#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...