| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1063086 | Ahmed57 | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
vector<int> adj[100001];
int sz[100001],dep[100001];
void precomp(int i,int pr){
sz[i] =1;
dep[i] = dep[pr]+1;
for(auto j:adj[i]){
if(j==pr)continue;
precomp(j,i);
sz[i]+=sz[j];
}
}
vector<pair<int,int>> typ[2];
void lol(int i,int pr,int uni,int passed,int de){
typ[passed].push_back({de,i});
for(auto j:adj[i]){
if(j==pr)continue;
lol(j,i,uni,passed|(j==uni),de+1);
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p,vector<int> q){
for(int i = 0;i<p.size();i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
int inda = 1 , indb = 2 , indc = 3;
if(a>b){swap(a,b);swap(inda,indb);}
if(b>c){swap(b,c);swap(indb,indc);}
if(a>b){swap(a,b);swap(inda,indb);}
if(b>c){swap(b,c);swap(indb,indc);}
precomp(0,0);
int nod = -1 , pr = -1;
int mi = 1e9;
for(int i = 0;i<n;i++){
for(auto j:adj[i]){
if(dep[j]<dep[i]){
if(sz[i]>=a&&mi>=sz[i]){
nod = i;
pr = j;
mi = sz[i];
}
}else{
if(n-sz[j]>=a&&mi>=n-sz[j]){
nod = i;
pr = j;
mi = n-sz[j];
}
}
}
}
if(n-mi>=b){
vector<int> ans(n,0);
int A = mi;
int B = n-mi;
lol(pr,pr,nod,0,1);
sort(typ[0].begin(),typ[0].end());
sort(typ[1].begin(),typ[1].end());
reverse(typ[0].begin(),typ[0].end());
reverse(typ[1].begin(),typ[1].end());
int lol = (n-mi)-b;
int val = c-lol;
for(int i = 0;i<typ[1].size();i++){
if(i<val)ans[typ[1][i].second] = indc;
else ans[typ[1][i].second] = inda;
}
for(int i = 0;i<typ[0].size();i++){
if(i<lol)ans[typ[1][i].second] = indc;
else ans[typ[1][i].second] = inda;
}
return ans;
}else{
vector<int> ans(n,0);
return ans;
}
}