oj.uz

Submission #972033

# Submission time Handle Problem Language Result Execution time Memory
972033 2024-04-29T19:01:55 Z opPO Split the Attractions (IOI19_split) C++14
40 / 100
 58 ms 17748 KB 
#include "split.h"
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

using namespace std;

void dfs(int v, vector<vector<int>> &g, vector<bool> &used, vector<int> &vec, int need) {
    if (sz(vec) >= need) return;
    if (used[v]) return;
    used[v] = 1;
    vec.push_back(v);
    for (int &u : g[v]) {
        if (used[u]) continue;
        dfs(u, g, used, vec, need);
    }
}

void tree(int v, vector<vector<int>> &g, vector<int> &siz, int p = -1) {
    siz[v] = 1;
    for (int &u : g[v]) {
        if (u == p) continue;
        tree(u, g, siz, v);
        siz[v] += siz[u];
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = sz(p);
	vector<int> res(n);

	vector<int> deg(n);
	vector<vector<int>> g(n);
	for (int i = 0; i < m; i++) {
        deg[p[i]]++;
        deg[q[i]]++;
        g[p[i]].push_back(q[i]);
        g[q[i]].push_back(p[i]);
	}
	int vert = 0;
	for (int i = 0; i < n; i++) {
        if (deg[i] < deg[vert]) {
            vert = i;
        }
	}

	vector<int> v = {0, a, b, c};
	vector<int> perm = {1, 2, 3};
	sort(all(perm), [&](int i, int j){
        return v[i] < v[j];
    });
    vector<bool> used(n);

    if (m == n - 1) {
        vector<int> siz(n);
        tree(0, g, siz);

        vector<int> A, B, C;
        for (int i = 0; i < m; i++) {
            int x = p[i], y = q[i];
            if (siz[x] > siz[y]) {
                swap(x, y);
            }

            if (siz[x] < n - siz[x]) {
                if (siz[x] >= v[perm[0]] && n - siz[x] >= v[perm[1]]) {
                    used[y] = 1;
                    dfs(x, g, used, A, v[perm[0]]);
                    used[y] = 0;
                    dfs(y, g, used, B, v[perm[1]]);
                    for (int ver = 0; ver < n; ver++) {
                        if (!used[ver]) {
                            C.push_back(ver);
                        }
                    }
                    break;
                }
            } else {
                if (n - siz[x] >= v[perm[0]] && siz[x] >= v[perm[1]]) {
                    used[y] = 1;
                    dfs(x, g, used, B, v[perm[1]]);
                    used[y] = 0;
                    dfs(y, g, used, A, v[perm[0]]);
                    for (int ver = 0; ver < n; ver++) {
                        if (!used[ver]) {
                            C.push_back(ver);
                        }
                    }
                    break;
                }
            }
        }

        if (sz(A) != v[perm[0]] || sz(B) != v[perm[1]] || sz(C) != v[perm[2]]) return res;
        for (int &i : A) {
            res[i] = perm[0];
        }
        for (int &i : B) {
            res[i] = perm[1];
        }
        for (int &i : C) {
            res[i] = perm[2];
        }

        return res;
    }

    vector<int> A;
    dfs(vert, g, used, A, v[perm[0]]);
    assert(sz(A) == v[perm[0]]);
    for (int &i : A) {
        res[i] = perm[0];
    }

    int unused = -1;
    for (int v = 0; v < n; v++) {
        if (!used[v]) {
            unused = v;
        }
    }
    assert(unused != -1);
    vector<int> B;
    dfs(unused, g, used, B, v[perm[1]]);
    assert(sz(B) == v[perm[1]]);
    for (int &i : B) {
        res[i] = perm[1];
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            res[i] = perm[2];
        }
    }

	return res;
}

/*
9 10
4 2 3
0 1
0 2
0 3
0 4
0 6
0 8
1 7
3 7
4 5
5 6
*/

/*
6 5
2 2 2
0 1
0 2
0 3
0 4
0 5
*/

/*
3 2
1 1 1
0 1
0 2
*/

/*
12 11
6 4 2
0 1
0 2
0 3
0 4
0 5
1 6
2 7
2 8
3 9
3 10
3 11
*/

/*
g++ -std=gnu++14 -O2 -Wall -pipe -static -o "split" "grader.cpp" "split.cpp"
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 51 ms 17748 KB ok, correct split
8 Correct 45 ms 15572 KB ok, correct split
9 Correct 46 ms 14816 KB ok, correct split
10 Correct 35 ms 9296 KB ok, correct split
11 Correct 41 ms 12504 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 45 ms 10924 KB ok, correct split
5 Correct 41 ms 10448 KB ok, correct split
6 Correct 34 ms 9308 KB ok, correct split
7 Correct 46 ms 15316 KB ok, correct split
8 Correct 58 ms 13136 KB ok, correct split
9 Correct 40 ms 9808 KB ok, correct split
10 Correct 34 ms 10440 KB ok, correct split
11 Correct 33 ms 10440 KB ok, correct split
12 Correct 33 ms 10708 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 44 ms 10436 KB ok, correct split
3 Correct 16 ms 4444 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 54 ms 13008 KB ok, correct split
6 Correct 45 ms 12824 KB ok, correct split
7 Correct 56 ms 12608 KB ok, correct split
8 Correct 48 ms 13832 KB ok, correct split
9 Correct 44 ms 12760 KB ok, correct split
10 Correct 15 ms 3420 KB ok, no valid answer
11 Correct 19 ms 4956 KB ok, no valid answer
12 Correct 44 ms 9940 KB ok, no valid answer
13 Correct 38 ms 9812 KB ok, no valid answer
14 Correct 37 ms 10196 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 51 ms 17748 KB ok, correct split
8 Correct 45 ms 15572 KB ok, correct split
9 Correct 46 ms 14816 KB ok, correct split
10 Correct 35 ms 9296 KB ok, correct split
11 Correct 41 ms 12504 KB ok, correct split
12 Correct 0 ms 348 KB ok, correct split
13 Correct 1 ms 348 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 45 ms 10924 KB ok, correct split
16 Correct 41 ms 10448 KB ok, correct split
17 Correct 34 ms 9308 KB ok, correct split
18 Correct 46 ms 15316 KB ok, correct split
19 Correct 58 ms 13136 KB ok, correct split
20 Correct 40 ms 9808 KB ok, correct split
21 Correct 34 ms 10440 KB ok, correct split
22 Correct 33 ms 10440 KB ok, correct split
23 Correct 33 ms 10708 KB ok, correct split
24 Correct 1 ms 348 KB ok, correct split
25 Correct 44 ms 10436 KB ok, correct split
26 Correct 16 ms 4444 KB ok, correct split
27 Correct 1 ms 348 KB ok, correct split
28 Correct 54 ms 13008 KB ok, correct split
29 Correct 45 ms 12824 KB ok, correct split
30 Correct 56 ms 12608 KB ok, correct split
31 Correct 48 ms 13832 KB ok, correct split
32 Correct 44 ms 12760 KB ok, correct split
33 Correct 15 ms 3420 KB ok, no valid answer
34 Correct 19 ms 4956 KB ok, no valid answer
35 Correct 44 ms 9940 KB ok, no valid answer
36 Correct 38 ms 9812 KB ok, no valid answer
37 Correct 37 ms 10196 KB ok, no valid answer
38 Runtime error 1 ms 600 KB Execution killed with signal 6
39 Halted 0 ms 0 KB -