| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 786249 | resting | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/std++.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;
}