| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1283716 | tcmduc | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const long long oo=1e18;
const int mod=1e9+7;
void home()
{
freopen("main.inp","r",stdin);
freopen("main.out","w",stdout);
}
bool bit(int mask,int i){return (mask>>i)&1;}
int on(int mask,int i){return mask|(1<<i);}
int n,m;
pair<int,int>mau[5];
vector<int>a[100005];
int sz[100005];
int pick=0;
bool vis[100005];
void DFS(int u)
{
sz[u]=1;vis[u]=true;
for(int v:a[u])
{
if(!vis[v])
{
DFS(v);
sz[u]+=sz[v];
}
}
if(!pick&&sz[u]>=mau[1].fi&&n-sz[u]>=mau[2].fi)pick=u;
}
int cl[100005];
queue<int>q;
int deg[100005];
void TraceA(int u,bool ok)
{
if(ok)cl[u]=1,mau[1].fi--;
vis[u]=true;
for(int v:a[u])
{
if(!vis[v])
{
deg[u]++;
TraceA(v,ok|(v==pick));
}
}
if(deg[u]==0&&cl[u]==1)q.push(u);
}
void TraceB(int u)
{
if(!cl[u]&&mau[2].fi>0)cl[u]=2,mau[2].fi--;
vis[u]=true;
for(int v:a[u])
{
if(!vis[v]&&v!=pick)
TraceB(v);
}
}
void Tcmduc_VOI26()
{
cin>>n>>m;
cin>>mau[1].fi>>mau[2].fi>>mau[3].fi;mau[1].se=1;mau[2].se=2;mau[3].se=3;
sort(mau+1,mau+3+1);
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;u++,v++;
a[u].push_back(v);
a[v].push_back(u);
}
DFS(1);
memset(vis,0,sizeof(vis));
if(!pick)
{
for(int i=1;i<=n;i++)
cout<<0<<' ';
return;
}
TraceA(1,0|(pick==1));
memset(vis,0,sizeof(vis));
TraceB(1);
while(!q.empty())
{
int u=q.front();q.pop();
if(mau[1].fi==0)break;
cl[u]=0;mau[1].fi--;
for(int v:a[u])
{
deg[v]--;
if(deg[v]==0)q.push(v);
}
}
for(int i=1;i<=n;i++)
{
if(cl[i]==1)cout<<mau[1].se<<' ';
else if(cl[i]==2)cout<<mau[2].se<<' ';
else cout<<mau[3].se<<' ';
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//home();
Tcmduc_VOI26();
return 0;
}