| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 379208 | 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
struct unionfind{
int n;
vi pa,sz;
int grp;
unionfind(int n):n(n){
pa.assign(n,-1);
sz.assign(n,1);
rep(i,n) pa[i]=i;
grp=n;
}
int root(int x){
if(x==pa[x]) return x;
return pa[x]=root(pa[x]);
}
void unite(int x,int y){
x=root(x);y=root(y);
if(x==y) return;
if(sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x];
pa[x]=y;
grp--;
}
};
mt19937 rnd;
void gen(){
int n=rnd()%5+3;
int a=1;
int b=rnd()%(n-2)+1;
int c=n-a-b;
int m=n-1;
vi v;rep(i,n) v.pb(i);
shuffle(all(v),rnd);
vec<int>p,q;
rep(i,n-1) p.push_back(i),q.pb(i+1);
rng(i,n-1,m){
int x=rnd()%n,y=rnd()%n;
while(x==y) y=rnd()%n;
p.pb(x);q.pb(y);
}
vec<int> ans=find_split(n,a,b,c,p,q);
unionfind uf(n);
rep(i,m){
if(ans[p[i]]==2&&ans[q[i]]==2) uf.unite(p[i],q[i]);
}
int k=-1;
rep(i,n) if(ans[i]==2) k=i;
if(k<0) {
cout<<n<<" "<<m<<endl;
cout<<a<<" "<<b<<" "<<c<<endl;
rep(i,m){
cout<<p[i]<<" "<<q[i]<<endl;
}
for(auto g:ans) cout<<g;
cout<<endl;
exit(0);
}
int on=0,th=0,tw=0;
rep(i,n) if(ans[i]==2){
tw++;
if(uf.root(i)!=uf.root(k)){
cout<<n<<" "<<m<<endl;
cout<<a<<" "<<b<<" "<<c<<endl;
rep(i,m){
cout<<p[i]<<" "<<q[i]<<endl;
}
for(auto g:ans) cout<<g;
cout<<endl;
exit(0);
}
}
rep(i,n){
if(ans[i]==1) on++;
if(ans[i]==3) th++;
}
if(on!=1||th!=c||tw!=b){
cout<<n<<" "<<m<<endl;
cout<<a<<" "<<b<<" "<<c<<endl;
rep(i,m){
cout<<p[i]<<" "<<q[i]<<endl;
}
for(auto g:ans) cout<<g;
cout<<endl;
exit(0);
}
}
void check(){
rep(i,1000000){
gen();
cout<<i<<endl;
}
}
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);
int tw=2,twi=b;
int mn=min({a,b,c}),nxt=b;
if(a==mn){
if(b>c) tw=3,twi=c,nxt=c;
}
else if(b==mn) {
if(a<c) tw=1,twi=a,nxt=a;
else tw=3,twi=c,nxt=c;
}
else {
if(a<b) tw=1,twi=a,nxt=a;
}
rep(i,n){
for(auto g:f[i]){
if(sz[g]>=min({a,b,c})&&n-sz[g]>=nxt||
sz[g]>=nxt&&n-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;
if(sz[g]>=nxt&&n-sz[g]>=min({a,b,c})){
swap(mn,tw);
swap(k,twi)l
}
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=tw,h=twi;
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){
queue<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);
}