Submission #1179591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179591		crafticat	Split the Attractions (IOI19_split)	C++20	0 / 100	66 ms	21168 KiB

split

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n;i++)
#define FOR(i,j,n) for (int i = j;i < n;i++)
template<typename T>
using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;

void computeSiz(V<vi> &tree, int x, int p, vi &siz, vi &par) {
    siz[x] = 1;
    par[x] = p;

    for (auto y : tree[x]) {
        if (y == p) continue;
        computeSiz(tree, y, x, siz, par);
        siz[x] += siz[y];
    }
}

void dfs(V<vi> &tree, int x, int p, V<bool> &vis, vi &order) {
    vis[x] = 1;
    order.push_back(x);

    for (auto y : tree[x]) {
        if (y == p) continue;
        dfs(tree, y, x, vis, order);
    }
}

vi checkTree(V<vi> &tree, int a, int b, int root) {
    vi siz(tree.size());
    vi par(tree.size());

    computeSiz(tree, root, -1, siz, par);

    F0R(i, tree.size()) {
        if (siz[i] >= a and (tree.size() - siz[i] >= b)) {
            V<bool> typeA(tree.size());
            vi order;
            vi ans(tree.size());

            int amountA = 0, amountB = 0;

            dfs(tree, i, par[i], typeA, order);

            for (auto x : order) {
                if (amountA < a) {
                    amountA++;
                    ans[x] = 1;
                } else
                    ans[x] = 3;
            }

            F0R(j, tree.size()) {
                if (typeA[j]) continue;
                if (amountB < b) {
                    amountB++;
                    ans[j] = 2;
                } else ans[j] = 3;
            }
            if (amountA != a or amountB != b) exit(6);

            return ans;
        }
    }

    return {};
}

V<vi> createG(vi p, vi q, int n) {
    V<vi> g(n);
    F0R(i, p.size()) {
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
    }
    return g;
}
V<vi> g;

void dfsOrder(int x, V<bool> &vis, vi &p, vi &q) {
    vis[x] = 1;

    for (auto y : g[x]) {
        if (vis[y]) continue;
        p.push_back(x);
        q.push_back(y);
        dfsOrder(y, vis, p, q);
    }
}

int findDiff(int x, int y) {
    if (x == 1 and y == 2) return 3;
    if (x == 2 and y == 3) return 1;
    if (x == 1 and y == 3) return 2;
    exit(2);
}

std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
    g = createG(p, q, n);
    V<pi> comb = {{a,b}, {b,c}, {c,a}, {b,a}, {c,b}, {a,c}};

    int i = 0;
        V<bool> vis(n);
        vi x, y;
        dfsOrder(i, vis, x,y);

        V<vi> tree = createG(x, y, n);
        for (auto [aSiz,bSiz] : comb) {
            vi ans = checkTree(tree, aSiz, bSiz, i);
            if (!ans.empty()) {
                vi recolor(n);
                map<int, int> to;
                if (a == aSiz) to[1] = 1;
                if (aSiz == b) to[1] = 2;
                if (aSiz == c) to[1] = 3;
                if (bSiz == c) to[2] = 3;
                if (bSiz == b) to[2] = 2;
                if (a == bSiz) to[2] = 1;

                to[3] = findDiff(min(to[1], to[2]), max(to[1], to[2]));

                F0R(i, n)
                    recolor[i] = to[ans[i]];
                return recolor;
            }
        }


    vi emptyAns(n);
    return emptyAns;
}

#if DEBUG

int main() {
    int n, m, a, b, c;
    assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
    vector<int> p(m), q(m);
    for (int i=0; i<m; i++)
        assert(2 == scanf("%d%d", &p[i], &q[i]));
    fclose(stdin);

    vector<int> result = find_split(n, a, b, c, p, q);

    for (int i=0; i<(int)result.size(); i++)
        printf("%s%d", ((i>0)?" ":""), result[i]);
    printf("\n");
    fclose(stdout);
    return 0;
}
#endif

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36