| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 645211 | dattranxxx | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 1e5 + 5;
vector<int> adj[N], child[N];
int n, m; pair<int, int> x[3];
int low[N], in[N], siz[N], t = 0;
vector<int> ans;
int dfs1(int u, pair<int, int>& x) {
ans[u] = x.se; x.fi--;
if (x.fi == 0) return 1;
for (int v : child[u])
if (dfs1(v, x)) return 1;
return 0;
}
int dfs2(int u, pair<int, int>& y) {
ans[u] = y.se; y.fi--;
if (y.fi == 0) return 1;
for (int v : adj[u]) if (ans[v] == x[2].se)
if (dfs2(v, y)) return 1;
return 0;
}
int dfs(int u, int p = -1) {
int flag = 1;
in[u] = low[u] = ++t, siz[u] = 1;
for (int v : adj[u]) if (v != p) {
if (in[v]) low[u] = min(low[u], in[v]); // back-edge
else {
child[u].emplace_back(v);
if (dfs(v, u)) return 1;
low[u] = min(low[u], low[v]);
siz[u] += siz[v];
flag &= siz[v] < x[0].fi;
}
}
flag &= siz[u] >= x[0].fi;
if (!flag)
return 0;
int P1 = siz[u], P2 = n - siz[u];
for (int v : child[u]) if (low[v] < in[u] && P2 < x[0].fi)
P1 -= siz[v], P2 += siz[v];
if (P2 < x[0].fi)
return 0;
if (P1 > P2) swap(x[0], x[1]);
dfs1(u, x[0]); dfs2(p, x[1]);
return 1;
}
vector<int> find_split(int _n, int a, int b, int c, vector<int>& p, vector<int>& q) {
n = _n; m = p.size();
x[0] = {a, 1}, x[1] = {b, 2}, x[2] = {c, 3};
sort(x, x + 3);
for (int i = 0, u, v; i < m; ++i)
u = p[i], v = q[i],
adj[u].emplace_back(v),
adj[v].emplace_back(u);
ans = vector<int>(n, x[2].se);
if (dfs(0))
return ans;
return vector<int>(n, 0);
}