| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 198413 | FerThugGato12500 | 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<string.h>
using namespace std;
vector<int> ed[11];
int need[3];
int n, m;
bool vis[100001];
int cld[11];
int dfs(int ind)
{
int D=1;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D+=dfs(ed[ind][i]);
return (cld[ind] = D);
}
int bus(int ind)
{
bool z=true;
vis[ind]=true;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]] && cld[ed[ind][i]]>=n/2)
z=false;
if(n-cld[ind]>=n/2)
z=false;
if(z) return ind;
int D=-1;
for(int i = 0; i < ed[ind].size(); i++)
if(!vis[ed[ind][i]])
D=max(bus(ed[ind][i]), D);
return D;
}
int centroide()
{
dfs(1);
memset(vis, false, sizeof(vis));
return bus(1);
}
vector<int> ans[3];
int rey;
typedef struct
{
int to, cld;
}Wasd;
bool operator < (const Wasd &a, const Wasd &b)
{
return a.cld < b.cld;
}
void expand(int ind)
{
vis[ind]=true;
ans[rey].push_back(ind);
if(ans[rey].size()==need[rey])
return;
vector<Wasd> ed2;
Wasd te;
for(int i = 0; i < ed[ind].size(); i++)
{
te.to=ed[ind][i];
te.cld=cld[te.to]-cld[ind];
if(te.cld<0) te.cld=cld[te.to];
ed2.push_back(te);
}
sort(ed2.begin(), ed2.end());
for(int i = 0; i < ed2.size(); i++)
if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
expand(ed2[i].to);
return;
}
int res[11];
int main()
{
int x, y;
cin>>n>>m>>need[0]>>need[1]>>need[2];
for(int i = 0; i < m; i++)
{
cin>>x>>y;
ed[x].push_back(y);
ed[y].push_back(x);
}
int cnt = centroide();
if(need[0]<=max(need[1], need[2]) && need[0]>=min(need[2], need[1]))
rey=0;
else if(need[1]<=max(need[0], need[2]) && need[1]>=min(need[2], need[0]))
rey=1;
else rey=2;
memset(vis, false, sizeof(vis));
expand(cnt);
if(need[0]<=need[1] && need[0]<=need[2])
rey=0;
else if(need[1]<=need[0] && need[1]<=need[2])
rey=1;
else rey=2;
for(int i = 0; i < n; i++)
if(!vis[i])
{
expand(i);
if(ans[rey].size()==need[rey])
break;
ans[rey].clear();
}
for(int k = 0; k < 3; k++)
for(int i = 0; i < ans[k].size(); i++)
res[ans[k][i]]=k+1;
if(ans[0].size()>0 && ans[1].size()>0)
rey=2;
else if(ans[1].size()>0 && ans[2].size()>0)
rey=0;
else rey=1;
for(int i = 0; i < n; i++)
if(res[i]==0)
cout<<rey+1<<" ";
else cout<<res[i]<<" ";
return 0;
}