| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379195 | Thistle | Split the Attractions (IOI19_split) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "split.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
#define pb emplace_back
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int m=siz(p);
vec<H>e(m);
rep(i,m){
e[i]=H{p[i],q[i]};
}
vec<vi>f(n);
rep(i,m) {
f[e[i].fs].pb(e[i].sc);
f[e[i].sc].pb(e[i].fs);
}
if(m==n-1){
vi sz(n,0);
auto dfs=[&](int x,int p,auto& dfs)->int{
sz[x]=1;
for(auto g:f[x]){
if(g==p) continue;
sz[x]+=dfs(g,x,dfs);
}
return sz[x];
};dfs(0,-1,dfs);
rep(i,n){
for(auto g:f[i]){
if(sz[g]>=min({a,b,c})){
queue<int>q;
q.push(g);
vec<int>used(n,0);
int k=0;
if(a<=b&&a<=c) k=1;
else if(b<=a&&b<=c) k=2;
else k=3;
used[g]=k;
int sum=1;
while(!q.empty()){
int t=q.front();q.pop();
for(auto g:f[t]){
if(g==i) continue;
if(!used[g]){
if(sum==min({a,b,c})) continue;
used[g]=k;
q.push(g);
sum++;
}
}
}
q.push(i);
sum=1;
int d=1,h=a;
if(d==k) d=2,h=b;
used[i]=d;
while(!q.empty()){
int t=q.front();q.pop();
for(auto g:f[t]){
if(!used[g]){
if(sum==h) continue;
used[g]=d;
q.push(g);
sum++;
}
}
}
int r=1;
if(d!=1&&k!=1) r=1;
else if(d!=2&&k!=2) r=2;
else r=3;
for(auto& g:used){
if(g==0) g=r;
}
return used;
}
}
}
return vec<int>(n,0);
}
if(a==1){
queueue<int>que;
que.push(0);
vec<int>used(n,0);
used[0]=2;int sum=1;
while(!que.empty()){
int t=que.front();que.pop();
for(auto g:f[t]){
if(!used[g]){
if(sum==b) continue;
used[g]=2;
que.push(g);
sum++;
}
}
}
rep(i,n) if(used[i]==0){
used[i]=1;
break;
}
rep(i,n) if(used[i]==0){
used[i]=3;
}
return used;
}
return vec<int>(n,0);
}