| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 880481 | ace_in_the_hole | 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.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define cst(T) const T&
template<class A, class B> bool umin(A& var, cst(B) val) {
return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
return (var < val) ? (var = val, true) : false;
}
typedef long long Int;
typedef long double Real;
const int MOD = 2004010501;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> Int random(const X& l, const Y& r) {
return uniform_int_distribution<Int>(l,r)(rng);
}
#define DBG(x) cerr << #x << " = " << x << ' ';
#define DBGn(x) cerr << #x << " = " << x << '\n';
const int N = 2e5 + 50;
int n,m, a,b,c;
int fr[N], to[N];
vector<int> adj[N];
int siz[N], pa[N], depth[N];
int ord[N], low[N], timer = 0, fin[N];
void dfs(int u) {
siz[u] = 1;
low[u] = ord[u] = ++timer;
for (auto v : adj[u]) if (v != pa[u]) {
if (!siz[v]) {
pa[v] = u;
depth[v] = depth[u] + 1;
dfs(v);
umin(low[u], low[v]);
siz[u] += siz[v];
} else umin(low[u], ord[v]);
}
fin[u] = timer;
}
int conf[N];
void mark_subtree(int u, int c) {
if (conf[u] == c) return ;
conf[u] = c;
for (auto v : adj[u])
if (pa[v] == u) mark_subtree(v,c);
}
void print() {
for (int u = 0; u < n; u++) cout << conf[u] << ' ';
}
void revalidate_colors(int t1, int t2) {
int r1 = count(conf, conf+n, 1) - t1;
int r2 = count(conf, conf+n, 2) - t2;
// cerr << " have " << r1+t1 << ", " << r2+t2 << ", goal: "; DBG(t1) DBGn(t2)
assert((min(r1,r2) >= 0));
vector<int> nodes(n);
iota(all(nodes), 0);
sort(all(nodes), [&] (int u, int v) {
return depth[u] > depth[v];
});
for (int u : nodes) {
bool ch = (conf[u] == 0);
if (conf[u] == 1 && r1 > 0) ch = 1, --r1;
else if (conf[u] == 2 && r2 > 0) ch = 1, --r2;
if (ch) conf[u] = 3;
}
for (int t = 1; t <= 3; t++)
cerr << "count(" << t << ") = " << count(conf, conf+n, t) << '\n';
print();
}
void solve(int testID) {
DBGn(testID);
cin >> n >> m;
// if (m != n-1) return ;
cin >> a >> b >> c;
if (a > b) swap(a,b);
if (a > c) swap(a,c);
if (b > c) swap(b,c);
assert((a + b + c == n && a <= b && b <= c));
for (int i = 1; i <= m; i++) {
int u,v;
cin >> u >> v;
fr[i] = u, to[i] = v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int root = random(0,n-1);
root = 0;
dfs(root);
int sub = -1;
for (int u = 0; u < n; u++)
if (sub == -1 or (u != root && siz[u] >= a && siz[u] < siz[sub])) sub = u;
DBGn(sub)
memset(conf, 0, sizeof(conf));
if (sub == -1) return print();
mark_subtree(root, 1);
mark_subtree(sub, 2);
if (n - siz[sub] >= a) {
if (siz[sub] >= b) return revalidate_colors(a,b);
assert(n - siz[sub] >= b);
return revalidate_colors(b,a);
}
cerr << "needs to modify\n";
// detachs
for (int u = 0; u < n; u++)
if (u != sub && ord[sub] <= ord[u] && ord[u] <= fin[sub])
mark_subtree(u, 1);
int sub_size = count(conf, conf+n, 2);
if (n - sub_size >= a) {
if (sub_size >= b) return revalidate_colors(a,b);
return revalidate_colors(b,a);
}
for (int i = 0; i < n; i++) cout << "0 ";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "WF"
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int numTests = 1;
// cin >> numTests;
for (int i = 1; i <= numTests; i++) solve(i);
}
// xq cute <3