| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 718320 | bebra | 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 dbg(x) cerr << #x << ": " << x << endl;
const int MAX_N = 1e5 + 5;
vector<int> g[MAX_N];
int color[MAX_N];
bool block[MAX_N];
int sz[MAX_N];
int n;
int order_color[3];
int order[3];
bool found = false;
void dfs_color(int v, int p, int c, int& cnt) {
if (cnt == 0) {
return;
}
--cnt;
color[v] = c;
for (auto u : g[v]) {
if (u == p || block[u]) continue;
dfs_color(u, v, c, cnt);
}
}
void dfs_calc(int v = 0, int p = -1) {
sz[v] = 1;
for (auto u : g[v]) {
if (u == p) continue;
dfs_calc(u, v);
sz[v] += sz[u];
if (found) return;
}
if (sz[v] >= order[0] && n - sz[v] >= order[1]) {
block[v] = true;
found = true;
int curr_cnt1 = order[0];
int curr_cnt2 = order[1];
dfs_color(v, -1, order_color[0], curr_cnt1);
dfs_color(0, -1, order_color[1], curr_cnt2);
return;
}
if (sz[v] >= order[1] && n - sz[v] >= order[0]) {
block[v] = true;
found = true;
int curr_cnt1 = order[0];
int curr_cnt2 = order[1];
dfs_color(v, -1, order_color[1], curr_cnt2);
dfs_color(0, -1, order_color[0], curr_cnt1);
return;
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n;
int m = p.size();
for (int i = 0; i < m; ++i) {
int u = p[i];
int v = q[i];
g[u].push_back(v);
g[v].push_back(u);
}
order[0] = a;
order[1] = b;
order[2] = c;
order_color[0] = 1;
order_color[1] = 2;
order_color[2] = 3;
sort(order_color, order_color + 3, [&](int lhs, int rhs) {
return order[lhs - 1] < order[rhs - 1];
});
sort(order, order + 3);
fill_n(color, n, order_color[2]);
dfs_calc();
vector<int> res(n);
for (int i = 0; i < n; ++i) {
res[i] = color[i];
}
return res;
}
int main() {
int m;
cin >> n >> m;
int a, b, c;
cin >> a >> b >> c;
vector<int> p(m), q(m);
for (int i = 0; i < m; ++i) {
cin >> p[i] >> q[i];
}
for (auto x : find_split(n, a, b, c, p, q)) {
cout << x << ' ';
}
cout << '\n';
}