「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[MAXN];

pair <int, int> lim[5];

bool instack[MAXN];

int n, m, cnt, size[MAXN], ans[MAXN];

int timer, dfn[MAXN], low[MAXN];

void dfs(int pos, int col, bool down) {

        if (cnt == 0 || ans[pos]) return;

        ans[pos] = col, cnt--;

        for (auto x : a[pos])

                if (!down || dfn[x] > dfn[pos]) dfs(x, col, down);

}

void tarjan(int pos, int fa) {

        instack[pos] = true;

        dfn[pos] = low[pos] = ++timer;

        int sum = 0; size[pos] = 1;

        vector <int> sons;

        for (auto x : a[pos])

                if (dfn[x] == 0) {

                        tarjan(x, pos);

                        sons.push_back(x);

                        chkmin(low[pos], low[x]);

                        size[pos] += size[x];

                        if (low[x] < dfn[pos]) sum += size[x];

                } else if (instack[x]) chkmin(low[pos], dfn[x]);

        if (size[pos] >= lim[1].first) {

                if (n - size[pos] + sum < lim[1].first) {

                        for (int i = 1; i <= n; i++)

                                printf("%d ", 0);

                        printf("\n");

                        exit(0);

                }

                if (n - size[pos] + sum < lim[2].first) swap(lim[1], lim[2]);

                int colx = lim[1].second, coly = lim[2].second;

                cnt = lim[1].first, ans[pos] = colx, cnt--;

                for (auto x : sons) if (low[x] >= dfn[pos]) dfs(x, colx, true);

                for (auto x : sons) if (low[x] < dfn[pos]) dfs(x, colx, true);

                assert(cnt == 0);

                cnt = lim[2].first;

                dfs(1, coly, false);

                assert(cnt == 0);

                for (int i = 1; i <= n; i++) {

                        if (ans == 0) ans = lim[3].second;

                        printf("%d ", ans);

                }

                printf("\n");

                exit(0);

        }

        instack[pos] = 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[1].first + lim[2].first + lim[3].first == n);

        for (int i = 1; i <= m; i++) {

                int x, y; read(x), read(y), x++, y++;

                a[x].push_back(y);

                a[y].push_back(x);

        }

        tarjan(1, 0);

        assert(false);

        return 0;

}