제출 #297731

#제출 시각아이디문제언어결과실행 시간메모리
297731amiratouSplit 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; bool g; 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){ //cerr<<node<<" , "; //cerr<<sz(vec[node])<<"\n"; sort(vec[node].begin(),vec[node].end(),comp); if(A==1 && sz(vec[node])>=1 && s[vec[node][0]]>=B)return node; if(sz(vec[node])==1)return solve(vec[node][0]); else if(sz(vec[node])>=2){ if(s[vec[node][0]]>=B && (s[vec[node][1]]+1)>=A)return node; else if(s[vec[node][0]]>=A && (s[vec[node][1]]+1)>=B){g=1;return node;} else if((s[vec[node][0]]<B && (s[vec[node][1]]+1)<A) && (s[vec[node][0]]<A && (s[vec[node][1]]+1)<B))return -1; s[node]-=s[vec[node][0]]; return solve(vec[node][0]); } 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); if(idx==-1) return res; //cerr<<idx<<"\n"; if(g){ res[idx]=c_b; if(B!=1)cnt=B-1,gimme(vec[idx][1],idx,1); cnt=A,gimme(vec[idx][0],idx); } else{ res[idx]=c_a; 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...