「IOI2019」景点划分
参考程序
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
vector <int> a;
pair <int, int> lim;
bool instack;
int n, m, cnt, size, ans;
int timer, dfn, low;
void dfs(int pos, int col, bool down) {
if (cnt == 0 || ans) return;
ans = col, cnt--;
for (auto x : a)
if (!down || dfn > dfn) dfs(x, col, down);
}
void tarjan(int pos, int fa) {
instack = true;
dfn = low = ++timer;
int sum = 0; size = 1;
vector <int> sons;
for (auto x : a)
if (dfn == 0) {
tarjan(x, pos);
sons.push_back(x);
chkmin(low, low);
size += size;
if (low < dfn) sum += size;
} else if (instack) chkmin(low, dfn);
if (size >= lim.first) {
if (n - size + sum < lim.first) {
for (int i = 1; i <= n; i++)
printf("%d ", 0);
printf("\n");
exit(0);
}
if (n - size + sum < lim.first) swap(lim, lim);
int colx = lim.second, coly = lim.second;
cnt = lim.first, ans = colx, cnt--;
for (auto x : sons) if (low >= dfn) dfs(x, colx, true);
for (auto x : sons) if (low < dfn) dfs(x, colx, true);
assert(cnt == 0);
cnt = lim.first;
dfs(1, coly, false);
assert(cnt == 0);
for (int i = 1; i <= n; i++) {
if (ans == 0) ans = lim.second;
printf("%d ", ans);
}
printf("\n");
exit(0);
}
instack = false;
}
int main() {
read(n), read(m);
for (int i = 1; i <= 3; i++) {
int x; read(x);
lim = make_pair(x, i);
}
sort(lim + 1, lim + 4);
assert(lim.first + lim.first + lim.first == n);
for (int i = 1; i <= m; i++) {
int x, y; read(x), read(y), x++, y++;
a.push_back(y);
a.push_back(x);
}
tarjan(1, 0);
assert(false);
return 0;
}
页:
[1]