oj.uz

Submission #143799

# Submission time Handle Problem Language Result Execution time Memory
143799 2019-08-15T07:43:03 Z imeimi2000 Split the Attractions (IOI19_split) C++17
0 / 100
 161 ms 15792 KB 
#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 = 1;
    {
        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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Incorrect 161 ms 15792 KB invalid split: #1=34079, #2=33333, #3=32588
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Incorrect 4 ms 2684 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB ok, correct split
2 Incorrect 127 ms 10016 KB invalid split: #1=20000, #2=1, #3=79999
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, no valid answer
3 Correct 5 ms 2680 KB ok, correct split
4 Correct 3 ms 2680 KB ok, correct split
5 Correct 5 ms 2680 KB ok, correct split
6 Correct 5 ms 2680 KB ok, correct split
7 Incorrect 2 ms 2680 KB invalid split: #1=4, #2=1, #3=7
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Incorrect 161 ms 15792 KB invalid split: #1=34079, #2=33333, #3=32588
8 Halted 0 ms 0 KB -