| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 645097 | dattranxxx | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector<int> adj[N];
int n, m;
void impossible() {
for (int v = 0; v < n; ++v)
cout << 0 << ' ';
exit(0);
}
int R = -1, t = 0; pair<int, int> x[3];
int low[N], in[N], siz[N];
vector<int> tri[N];
void build(int u) {
in[u] = low[u] = ++t;
int flag = 1; siz[u] = 1;
for (int v : adj[u])
if (in[v]) low[u] = min(low[u], in[v]);
else tri[u].emplace_back(v), build(v),
low[u] = min(low[u], low[v]), siz[u] += siz[v], flag &= siz[v] < x[0].first;
flag &= siz[u] >= x[0].first;
if (flag) R = u;
}
int res[N], ans[N];
void dfs(int u, int c) {
ans[u] = c;
for (int v : tri[u])
dfs(v, c);
}
int fixx(int u) {
res[u] = x[0].second; x[0].first--;
if (x[0].first == 0) return 1;
for (int v : tri[u]) if (ans[v] == x[0].second) {
if (fixx(v)) return 1;
}
return 0;
}
int fixy(int u) {
res[u] = x[1].second; x[1].first--;
if (x[1].first == 0) return 1;
for (int v : tri[u]) if (ans[v] == x[2].second) {
if (fixy(v)) return 1;
}
return 0;
}
void print() {
for (int v = 0; v < n; ++v) res[v] = x[2].second;
fixx(R); fixy(0);
for (int v = 0; v < n; ++v)
cout << res[v] << ' ';
exit(0);
}
int main() {
cin.tie(0)->sync_with_stdio(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < 3; ++i) cin >> x[i].first, x[i].second = i + 1;
sort(x, x + 3);
for (int i = 0, u, v; i < m; ++i)
cin >> u >> v,
adj[u].emplace_back(v),
adj[v].emplace_back(u);
build(0);
if (R == -1) impossible();
for (int v = 0; v < n; ++v) ans[v] = x[2].second;
dfs(R, x[0].second);
int P1 = siz[R], P2 = n - P1;
for (int v : tri[R]) if (low[v] < in[R]) {
if (P1 - siz[v] >= x[0].first) P1 -= siz[v], dfs(v, x[2].second);
}
if (P2 < x[0].first) impossible();
print();
return 0;
}