| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 786252 | resting | 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.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ss, sz, pp, tin, low, st, res; int time = 1;
vector<vector<int>> scc;
void dfs(int v, int p) {
low[v] = tin[v] = time++; pp[v] = p;
st.push_back(v);
for (auto& x : adj[v]) {
if (tin[x]) low[v] = min(low[v], tin[x]);
else {
dfs(x, v);
if (low[x] == v) {
scc.push_back({});
while (st.back() != v) { scc.back().push_back(st.back()); st.pop_back(); }
scc.push_back(v);
}
}
}
}
int dfs_fill(int v, int t, int amt) {
if (!amt || res[v]) return;
res[v] = t; amt--;
for (auto& x : adj[v]) amt = dfs_fill(v, t, amt);
return amt;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
int na = 1, nb = 2, nc = 3;
if (a > b) {
swap(a, b); swap(na, nb);
}
if (b > c) {
swap(b, c); swap(nb, nc);
}
if (a > b) {
swap(a, b); swap(nb, nc);//haha o(n) sorting OwO
}
sz = pp = tin = low = ss = res = vector<int>(n, 0);
int m = p.size();
for (int i = 0; i < m; i++) {
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
dfs(0, 0);
int mxv = 0, mxi = 0;
for (int i = 0; i < scc.size(); i++) {
int mxsz = 0;
for (auto& x : scc[i]) {
mxsz = max(mxsz, sz[x]);
ss[x] = 0;
}
for (auto& x : scc[i]) {
ss[x] += sz[x]; ss[pp[x]] -= sz[x];
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
for (auto& x : scc[i]) {
if (sz[x] >= n / 3) {
if (n - x > mxv) {
mxv = n - x; mxi = i;
goto end;
}
}
}
mxv = n / 3;mxi = i;
end:;
}
if (mxv < a) return res;
vector<int> mark1(n, 0);
int mxsz = 0;
for (auto& x : scc[mxi]) {
mark1[x] = 1;
mxsz = max(mxsz, sz[x]);
ss[x] = 0;
}
for (auto& x : scc[i]) {
ss[x] += sz[x]; ss[pp[x]] -= sz[x];
if (sz[x] == mxsz) ss[x] += n - sz[x];
}
for (auto& x : scc[i]) {
if (sz[x] >= n / 3) {
res[x] = na; a--;
for (auto& x : adj[x])
if (!mark1[x])
a = dfs_fill(x, na, a);
for (auto& x : scc[i])
if (!res[x])
b = dfs_fill(x, nb, b);
goto end;
}
}
end:;
for (auto& x : res)if (!x)x = nc;
return res;
}