| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 209918 | Segtree | 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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
namespace uf{
ll dat[100010];
void init(){
rep(i,100010)dat[i]=-1;
}
ll find(ll x){
return (dat[x]<0?x:find(dat[x]));
}
void unite(ll a,ll b){
a=find(a),b=find(b);
if(a==b)return;
if(-dat[a]<-dat[b])swap(a,b);
dat[a]+=dat[b];
dat[b]=a;
}
bool same(ll a,ll b){
a=find(a),b=find(b);
return a==b;
}
};
vector<ll> g[100010];
ll col[100010];
ll paint(ll x,ll from,ll rem,ll c){
if(~col[x])return rem;
if(rem<=0)return 0;
col[x]=c;
rem--;
for(auto y:g[x])if(y!=from){
rem=paint(y,x,rem,c);
}
return rem;
}
ll siz[100010],par[100010];
ll dfs(ll x,ll from){//部分木のサイズと親を求める
siz[x]=1;
par[x]=from;
for(auto y:g[x])if(y!=from){
siz[x]+=dfs(y,x);
}
return siz[x];
}
vector<int> find_split(int N,int A,int B,int C,vector<int> U,vector<int> V){
int M=U.size();
assert(M==N);
uf::init();
rep(i,M){
if(uf::same(U[i],V[i]))continue;
uf::unite(U[i],V[i]);
g[U[i]].push_back(V[i]);
g[V[i]].push_back(U[i]);
}
dfs(0,-1);
int finalcol[3];
{//A<=B<=Cにする
vector<P> v;
v.push_back(make_pair(A,1));
v.push_back(make_pair(B,2));
v.push_back(make_pair(C,3));
sort(all(v));
rep(i,3)finalcol[i]=v[i].second;
A=v[0].first;
B=v[1].first;
C=v[2].first;
}
rep(i,N)col[i]=-1;
bool done=0;
rep(i,N){
ll x=siz[i],y=N-siz[i];
if(A<=x&&B<=y){
paint(i,par[i],A,0);
paint(par[i],i,B,1);
done=1;
break;
}
if(A<=y&&B<=x){
paint(i,par[i],B,1);
paint(par[i],i,A,0);
done=1;
break;
}
}
if(done==0){//
vector<int> fans;
rep(i,N)fans.push_back(0);
return fans;
}
rep(i,N)if(col[i]==-1)col[i]=2;
rep(i,N){
col[i]=finalcol[col[i]];
}
vector<int> fans;
rep(i,N)fans.push_back(col[i]);
return fans;
}
int main(){
int n,m,a,b,c;
cin>>n>>m>>a>>b>>c;
vector<int> U,V;
rep(i,m){
ll u,v;
cin>>u>>v;
U.push_back(u);
V.push_back(v);
}
vector<int> fans=find_split(n,a,b,c,U,V);
for(auto t:fans)cout<<t;
cout<<endl;
}