| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 334570 | IgorI | Split the Attractions (IOI19_split) | C++17 | 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.
const long long MOD = 998244353;
const long long INF = 1e9;
const long long INFLL = 1e18;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef complex<double> cd;
#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define pb push_back
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL
int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};
string Yes[2] = {"No\n", "Yes\n"};
string YES[2] = {"NO\n", "YES\n"};
string Possible[2] = {"Impossible\n", "Possible\n"};
string POSSIBLE[2] = {"IMPOSSIBLE\n", "POSSIBLE\n"};
void dfs2(int v, int p, vi &vis, vvi &g, vi &col, int color, vi &sz, int cent)
{
vis[v] = 2;
col[v] = color;
for (auto u : g[v]) if (vis[u] != 2)
{
if ((sz[u] < sz[cent] && sz[u] < sz[cent]) || (sz[v] > sz[cent] && sz[u] > sz[cent]))
dfs2(u, v, vis, g, col, color, sz, cent);
}
}
void dfs(int v, int p, vi &vis, vi &sz, int ¢, int ¢p, vvi &g, int n)
{
vis[v] = 1;
sz[v] = 1;
for (auto u : g[v]) if (vis[u] == 0)
{
dfs(u, v, vis, sz, cent, centp, g, n);
sz[v] += sz[u];
}
if (cent == -1 && sz[v] * 2 >= n)
{
cent = v;
centp = p;
}
}
void dfs3(int v, int color, vi &vis, vi &col, vi &ans, int A, int &x, vvi &g)
{
vis[v] = 1;
if (x) ans[v] = A, x--;
for (auto u : g[v])
{
if (ans[u] == 0 && vis[u] == 0 && (color == -1 || (col[u] == color)))
{
dfs3(u, color, vis, col, ans, A, x, g);
}
}
}
vi find_split(int n, int a, int b, int c, vi p, vi q)
{
vvi g(n);
for (int i = 0; i < p.size(); i++)
{
g[p[i]].pb(q[i]);
g[q[i]].pb(p[i]);
}
int cent = -1, centp = -1;
vi vis(n), sz(n), col(n), croot(n);
dfs(0, 0, vis, sz, cent, centp, g, n);
int color = 1;
vis[cent] = 2;
for (auto u : g[cent]) if (vis[u] != 2 && sz[u] < sz[cent])
{
dfs2(u, cent, vis, g, col, color, sz, cent);
croot[color] = u;
color++;
}
if (centp != cent)
{
dfs2(centp, cent, vis, g, col, color, sz, cent);
croot[color] = centp;
}
//cout << "cent = " << cent << "\n";
//for (int i = 0; i < n; i++)
// cout << col[i] << " ";
//cout << "\n";
vector<pii> s = {{a, 1}, {b, 2}, {c, 3}};
sort(all(s));
int A = s[0].first;
vector<int> ans(n);
vector<int> cnt(n);
for (int i = 0; i < n; i++)
cnt[col[i]]++;
for (int i = 1; i < n; i++)
{
if (cnt[i] >= A)
{
//cout << i << ", " << croot[i] << "\n";
int x = s[0].first;
vis = vi(n, 0);
dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
x = s[1].first;
vis = vi(n, 0);
dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
for (int j = 0; j < n; j++)
if (ans[j] == 0) ans[j] = s[2].second;
return ans;
}
}
vector<vector<int> > groups(n);
for (int i = 0; i < n; i++)
{
groups[col[i]].push_back(i);
}
for (int j = 0; j < p.size(); j++)
{
int f = p[j], t = q[j];
if (f != cent && t != cent && col[f] != col[t])
{
int c1 = col[f];
int c2 = col[t];
if (groups[c1].size() < groups[c2].size())
{
for (auto v : groups[c1])
col[v] = c2, groups[c2].push_back(v);
}
else
{
for (auto v : groups[c2])
col[v] = c1, groups[c1].push_back(v);
}
if (groups[c1].size() >= A)
{
int i = c1;
int x = s[0].first;
vis = vi(n, 0);
dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
x = s[1].first;
vis = vi(n, 0);
dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
for (int j = 0; j < n; j++)
if (ans[j] == 0) ans[j] = s[2].second;
return ans;
}
if (groups[c2].size() >= A)
{
int i = c2;
int x = s[0].first;
vis = vi(n, 0);
dfs3(croot[i], i, vis, col, ans, s[0].second, x, g);
x = s[1].first;
vis = vi(n, 0);
dfs3(cent, -1, vis, col, ans, s[1].second, x, g);
for (int j = 0; j < n; j++)
if (ans[j] == 0) ans[j] = s[2].second;
return ans;
}
}
}
return ans;
}
int main()
{
int n, m, a, b, c;
cin >> n >> m >> a >> b >> c;
vector<int> p(m), q(m);
for (int i = 0; i < m; i++)
cin >> p[i] >> q[i];
vector<int> ans = find_split(n, a, b, c, p, q);
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
cout << "\n";
}