oj.uz

Submission #220040

# Submission time Handle Problem Language Result Execution time Memory
220040 2020-04-06T20:56:00 Z VEGAnn Split the Attractions (IOI19_split) C++14
40 / 100
 146 ms 23544 KB 
#include <bits/stdc++.h>
#include "split.h"
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 100100;
vector<int> res;
vector<int> g[N], vc, children[N];
bool mrk[N];
int A[3], C[3], mrk_col[N], h[N], mn_h[N], pr[N], siz[N], mem = 0;

void dfs(int v, int p){
    pr[v] = p;
    siz[v] = 1;
    mrk[v] = 1;
    mn_h[v] = h[v];

    for (int u : g[v]){
        if (mrk[u]) continue;
        children[v].PB(u);
        h[u] = h[v] + 1;

        dfs(u, v);

        mn_h[v] = min(mn_h[v], mn_h[u]);
        siz[v] += siz[u];
    }
}

void col(int v, int cl){
    mrk_col[v] = cl;

    for (int u : children[v])
        col(u, cl);
}

void DFS(int v, int cl, int rlc){
    if (mrk[v]) return;
    if (mem == 0) return;

    mem--;
    mrk[v] = 1;
    res[v] = rlc;

    for (int u : g[v])
        if (mrk_col[u] == cl)
            DFS(u, cl, rlc);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);
	fill(all(res), 0);

	for (int i = 0; i < sz(p); i++){
        g[p[i]].PB(q[i]);
        g[q[i]].PB(p[i]);
	}

	A[0] = a; A[1] = b; A[2] = c;
	C[0] = 1; C[1] = 2; C[2] = 3;

	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}
	if (A[1] > A[2]) {
        swap(A[1], A[2]);
        swap(C[1], C[2]);
	}
	if (A[0] > A[1]) {
        swap(A[0], A[1]);
        swap(C[0], C[1]);
	}

    dfs(0, -1);

    for (int v = 0; v < n; v++){
        bool ok = bool(siz[v] >= a);

        for (int u : children[v])
            ok &= bool(siz[u] < a);

        if (!ok) continue;

        col(0, 1);
        col(v, 2);

        int real_siz = siz[v];

        for (int u : children[v])
            if (mn_h[u] < h[v] && real_siz - siz[u] >= a){
                real_siz -= siz[u];
                col(u, 1);
            }

        for (int t1 = 0; t1 < 2; t1++){
            int t2 = 1 - t1;

            if (real_siz >= A[t1] && n - real_siz >= A[t2]){
                fill(mrk, mrk + n, 0);

                mem = A[t2];
                DFS(pr[v], 1, C[t2]);

                mem = A[t1];
                DFS(v, 2, C[t1]);

                for (int &cr : res)
                    if (cr == 0)
                        cr = C[2];

                return res;
            }
        }
    }

	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 8 ms 5120 KB ok, correct split
6 Correct 7 ms 4992 KB ok, correct split
7 Correct 120 ms 23160 KB ok, correct split
8 Correct 105 ms 20856 KB ok, correct split
9 Correct 122 ms 20216 KB ok, correct split
10 Correct 111 ms 23544 KB ok, correct split
11 Correct 123 ms 23544 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 139 ms 19320 KB ok, correct split
5 Correct 100 ms 14328 KB ok, correct split
6 Correct 108 ms 23544 KB ok, correct split
7 Correct 121 ms 20728 KB ok, correct split
8 Correct 146 ms 16888 KB ok, correct split
9 Correct 105 ms 15736 KB ok, correct split
10 Correct 68 ms 13424 KB ok, correct split
11 Correct 65 ms 13424 KB ok, correct split
12 Correct 64 ms 13424 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 103 ms 14328 KB ok, correct split
3 Correct 35 ms 8832 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 115 ms 18296 KB ok, correct split
6 Correct 112 ms 18040 KB ok, correct split
7 Correct 128 ms 17912 KB ok, correct split
8 Correct 118 ms 19192 KB ok, correct split
9 Correct 117 ms 17656 KB ok, correct split
10 Correct 31 ms 8192 KB ok, no valid answer
11 Correct 44 ms 9600 KB ok, no valid answer
12 Correct 75 ms 13684 KB ok, no valid answer
13 Correct 94 ms 14200 KB ok, no valid answer
14 Correct 62 ms 13424 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5248 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 8 ms 5120 KB ok, correct split
6 Correct 7 ms 4992 KB ok, correct split
7 Correct 120 ms 23160 KB ok, correct split
8 Correct 105 ms 20856 KB ok, correct split
9 Correct 122 ms 20216 KB ok, correct split
10 Correct 111 ms 23544 KB ok, correct split
11 Correct 123 ms 23544 KB ok, correct split
12 Correct 7 ms 4992 KB ok, correct split
13 Correct 7 ms 4992 KB ok, correct split
14 Correct 8 ms 5120 KB ok, correct split
15 Correct 139 ms 19320 KB ok, correct split
16 Correct 100 ms 14328 KB ok, correct split
17 Correct 108 ms 23544 KB ok, correct split
18 Correct 121 ms 20728 KB ok, correct split
19 Correct 146 ms 16888 KB ok, correct split
20 Correct 105 ms 15736 KB ok, correct split
21 Correct 68 ms 13424 KB ok, correct split
22 Correct 65 ms 13424 KB ok, correct split
23 Correct 64 ms 13424 KB ok, correct split
24 Correct 7 ms 4992 KB ok, correct split
25 Correct 103 ms 14328 KB ok, correct split
26 Correct 35 ms 8832 KB ok, correct split
27 Correct 7 ms 4992 KB ok, correct split
28 Correct 115 ms 18296 KB ok, correct split
29 Correct 112 ms 18040 KB ok, correct split
30 Correct 128 ms 17912 KB ok, correct split
31 Correct 118 ms 19192 KB ok, correct split
32 Correct 117 ms 17656 KB ok, correct split
33 Correct 31 ms 8192 KB ok, no valid answer
34 Correct 44 ms 9600 KB ok, no valid answer
35 Correct 75 ms 13684 KB ok, no valid answer
36 Correct 94 ms 14200 KB ok, no valid answer
37 Correct 62 ms 13424 KB ok, no valid answer
38 Incorrect 7 ms 5248 KB jury found a solution, contestant did not
39 Halted 0 ms 0 KB -