| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 823894 | Blagoj | Split the Attractions (IOI19_split) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "split.h"
#include "grader.cpp"
using namespace std;
const int N = 1e5 + 5;
int tin[N], low[N], timer = 0, mark[N], sz[N], A, B, C, n;
bool special[N];
vector<int> g[N], children[N];
bool found = 0;
void color1(int cur, int type, int &Left) {
if (Left == 0) mark[cur] = 3;
else {
mark[cur] = type;
Left--;
}
for (auto next : children[cur]) color1(next, type, Left);
}
void color2(int cur, int type, int &Left) {
if (Left == 0) mark[cur] = 3;
else {
mark[cur] = type;
Left--;
}
for (auto next : g[cur]) if (mark[next] == 0) color2(next, type, Left);
}
void dfs(int cur) {
tin[cur] = low[cur] = ++timer;
sz[cur] = 1;
for (auto next : g[cur]) {
if (tin[next] == 0) {
dfs(next);
children[cur].push_back(next);
sz[cur] += sz[next];
low[cur] = min(low[cur], low[next]);
}
else low[cur] = min(low[cur], tin[next]);
}
if (found) return;
if (sz[cur] >= A) {
int sum = sz[cur];
for (auto next : children[cur]) {
if (low[next] < tin[cur] && sum - sz[next] >= A) {
sum -= sz[next];
special[next] = 1;
}
}
if (sum >= A && n - sum >= B) {
found = 1;
mark[cur] = 1;
int Left = A - 1;
for (auto next : children[cur]) {
if (!special[next]) color1(next, 1, Left);
}
color2(0, 2, B);
}
else if (sum >= B && n - sum >= A) {
found = 1;
mark[cur] = 2;
int Left = B - 1;
for (auto next : children[cur]) {
if (!special[next]) color1(next, 2, Left);
}
color2(0, 1, A);
}
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n;
vector<pair<int, int>> srt = {{-1, 0}, {a, 1}, {b, 2}, {c, 3}};
sort(srt.begin(), srt.end());
A = srt[1].first;
B = srt[2].first;
C = srt[3].first;
for (int i = 0; i < p.size(); i++) {
g[p[i]].push_back(q[i]);
g[q[i]].push_back(p[i]);
}
dfs(0);
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = srt[mark[i]].second;
return ans;
}