Submission #143800

#	Time	Username	Problem	Language	Result	Execution time	Memory
143800		imeimi2000	Split the Attractions (IOI19_split)	C++17	100 / 100	243 ms	16068 KiB

split

#include "split.h"
#include <vector>

using namespace std;

struct {
    int par[100000];
    int sz[100000];
    void init(int n) {
        for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1;
    }
    int find(int x) {
        if (par[x] != x) return par[x] = find(par[x]);
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        par[y] = x;
        sz[x] += sz[y];
        return 1;
    }
    int size(int x) {
        return sz[find(x)];
    }
} uf;

bool inTree[200000];
vector<int> edge[100000];
int sz[100000];

void dfs1(int x, int p) {
    sz[x] = 1;
    for (int i : edge[x]) {
        if (i == p) continue;
        dfs1(i, x);
        sz[x] += sz[i];
    }
}

int group[100000];
int dfs2(int x, int p, int g) {
    group[x] = g;
    int sz = 1;
    for (int i : edge[x]) {
        if (i == p) continue;
        sz += dfs2(i, x, g);
    }
    return sz;
}

bool choose[100000];
int dfs3(int x, int p, int a) {
    choose[x] = 1;
    if ((a -= sz[x]) <= 0) return a;
    for (int i : edge[x]) {
        if (i == p) continue;
        a = dfs3(i, x, a);
        if (a <= 0) return a;
    }
    return a;
}

bool ab[100000];
vector<int> ret;

int dfs4(int x, int p, int a, int c1, int c2) {
    if (a > 0) ret[x] = c1, --a;
    else ret[x] = c2;
    for (int i : edge[x]) {
        if (i == p) continue;
        a = dfs4(i, x, a, c1, c2);
    }
    return a;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int val[3] = { a, b, c };
    int col[3] = { 1, 2, 3 };
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (val[j] > val[j + 1]) {
                swap(val[j], val[j + 1]);
                swap(col[j], col[j + 1]);
            }
        }
    }
    uf.init(n);
    int m = p.size();
    for (int i = 0; i < m; ++i) {
        if (uf.merge(p[i], q[i])) {
            inTree[i] = 1;
            edge[p[i]].push_back(q[i]);
            edge[q[i]].push_back(p[i]);
        }
    }
    dfs1(0, -1);
    int cent = 0;
    {
        int p = -1, loop = 1;
        while (loop) {
            loop = 0;
            for (int i : edge[cent]) {
                if (i == p) continue;
                if (n < (sz[i] << 1)) {
                    p = cent;
                    cent = i;
                    loop = 1;
                    break;
                }
            }
        }
    }
    int k = 0;
    for (int i : edge[cent]) {
        sz[k] = dfs2(i, cent, k);
        uf.par[k] = k;
        uf.sz[k] = sz[k];
        ++k;
    }
    for (int i = 0; i < k; ++i) edge[i].clear();
    for (int i = 0; i < m; ++i) {
        if (inTree[i]) continue;
        if (p[i] == cent || q[i] == cent) continue;
        int x = group[p[i]];
        int y = group[q[i]];
        if (uf.merge(x, y)) {
            edge[x].push_back(y);
            edge[y].push_back(x);
        }
    }
    int r = -1;
    for (int i = 0; i < k; ++i) {
        if (uf.find(i) != i) continue;
        if (uf.size(i) < val[0]) continue;
        r = i;
        break;
    }
    if (r == -1) return vector<int>(n, 0);
    dfs3(r, -1, val[0]);
    for (int i = 0; i < n; ++i) ab[i] = !choose[group[i]];
    ab[cent] = 1;
    for (int i = 0; i < n; ++i) edge[i].clear();
    uf.init(n);
    for (int i = 0; i < m; ++i) {
        if (ab[p[i]] != ab[q[i]]) continue;
        if (uf.merge(p[i], q[i])) {
            edge[p[i]].push_back(q[i]);
            edge[q[i]].push_back(p[i]);
        }
    }
    ret.resize(n, 0);
    for (int i = 0; i < n; ++i) {
        if (ret[i]) continue;
        dfs4(i, -1, val[ab[i]], col[ab[i]], col[2]);
    }
    return ret;
}

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