| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 202039 | HellAngel | 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 <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 100007;
int ans, sz[maxn], n, m;
int col[maxn];
pair<int, int> a[4];
vector<int> vt[maxn];
void DFS(int u, int p)
{
sz[u] = 1;
for(auto v: vt[u])
{
if(v != p)
{
DFS(v, u);
sz[u] += sz[v];
}
}
}
int FindCen(int u, int p)
{
int Big = -1;
bool ok = true;
for(auto v: vt[u])
{
if(v == p) continue;
if(sz[v] * 2 > sz[1]) ok = false;
if(Big == -1 || sz[Big] < sz[v]) Big = v;
}
if(ok) return u;
return FindCen(Big, u);
}
void Solve(int cur, int par, int type1, int type2)
{
vector<int> ahihi;
queue<pair<int, int>> q;
q.emplace(cur, par);
while(!q.empty())
{
pair<int, int> p = q.front();
q.pop();
ahihi.push_back(p.first);
for(auto i: vt[p.first])
{
if(i == p.second) continue;
q.emplace(i, p.first);
}
}
for(int i = 0; i < ahihi.size(); i++)
{
if(i < a[type1].first) col[ahihi[i]] = a[type1].second;
else col[ahihi[i]] = a[type2].second;
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
cin >> n >> m >> a[1].first >> a[2].first >> a[3].first;
a[1].second = 1;
a[2].second = 2;
a[3].second = 3;
sort(a + 1, a + 4);
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
vt[u].push_back(v);
vt[v].push_back(u);
}
DFS(1, 1);
int root = FindCen(1, 1);
DFS(root, root);
int nxt = -1;
for(auto i: vt[root])
{
if(sz[i] >= a[1].first)
{
if(nxt == -1 || sz[nxt] > sz[i]) nxt = i;
}
}
if(nxt == -1)
{
for(int i = 1; i <= n; i++) cout << 0 << ' ';
exit(0);
}
Solve(nxt, root, 1, 3);
Solve(root, nxt, 2, 3);
for(int i = 1; i <= n; i++)
{
cout << col[i] << ' ';
}
}