oj.uz

Submission #1116854

# Submission time Handle Problem Language Result Execution time Memory
1116854 2024-11-22T13:24:15 Z byebye75 Mergers (JOI19_mergers) C++14
24 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
#define int long long int
#define vii vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define ff first
#define ss second

using namespace std;

const int N = 5e5 + 69;
const int K = 52;

int n, k;
int a[N], cnt[N], up[N], is_leaf[N];
vii g[N], c[K], t[N];
int have[N][K];

void dfs(int v, int p) {
    have[v][a[v]] = 1;
    for (auto u : g[v]) {
        if (u == p) continue;
        dfs(u, v);
        for (int j = 1; j <= k; j++) {
            have[v][j] += have[u][j];
        }
    }
    int ok = 1;
    for (int j = 1; j <= k; j++) {
        if (have[v][j] > 0)
            ok &= (have[v][j] == (int)c[j].size());
    }
    cnt[v] = ok;
}

void build(int v, int p, int c_node) {
    int x = c_node;
    if (cnt[v] && v > 1) {
        t[v].push_back(c_node);
        t[c_node].push_back(v);
        up[v] = c_node;
        x = v;
    }
    for (auto u : g[v]) {
        if (u == p) continue;
        build(u, v, x);
    }
}

void calc(int v, int p) {
    if (t[v].size() == 1 && v > 1)
        is_leaf[v] = 1;
    for (auto u : t[v]) {
        if (u == p) continue;
        calc(u, v);
        is_leaf[v] += is_leaf[u];
    }
}

signed main() {

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> k;

    // Clear previous test case data
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        t[i].clear();
        cnt[i] = is_leaf[i] = up[i] = 0;
        for (int j = 1; j <= k; j++) {
            have[i][j] = 0;
        }
    }
    for (int j = 1; j <= k; j++) {
        c[j].clear();
    }

    // Read tree edges
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // Read state assignments
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[a[i]].push_back(i);
    }

    dfs(1, 0);
    build(1, 0, 1);
    calc(1, 0);

    assert(cnt[1] == 1);

    int o = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] && t[i].size() == 1)
            o += 1;
    }

    int ans = (o + 1) / 2;
    cout << ans << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31056 KB Output is correct
2 Correct 5 ms 31084 KB Output is correct
3 Correct 6 ms 31312 KB Output is correct
4 Correct 5 ms 31056 KB Output is correct
5 Correct 5 ms 31056 KB Output is correct
6 Correct 5 ms 31056 KB Output is correct
7 Correct 5 ms 31056 KB Output is correct
8 Correct 5 ms 31056 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 27092 KB Output is correct
12 Correct 8 ms 31056 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 10 ms 24912 KB Output is correct
15 Correct 7 ms 31056 KB Output is correct
16 Correct 6 ms 24912 KB Output is correct
17 Correct 5 ms 24912 KB Output is correct
18 Correct 8 ms 24912 KB Output is correct
19 Correct 7 ms 24912 KB Output is correct
20 Correct 7 ms 24968 KB Output is correct
21 Correct 6 ms 25168 KB Output is correct
22 Correct 9 ms 25168 KB Output is correct
23 Correct 8 ms 24912 KB Output is correct
24 Correct 8 ms 25048 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31056 KB Output is correct
2 Correct 5 ms 31084 KB Output is correct
3 Correct 6 ms 31312 KB Output is correct
4 Correct 5 ms 31056 KB Output is correct
5 Correct 5 ms 31056 KB Output is correct
6 Correct 5 ms 31056 KB Output is correct
7 Correct 5 ms 31056 KB Output is correct
8 Correct 5 ms 31056 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 27092 KB Output is correct
12 Correct 8 ms 31056 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 10 ms 24912 KB Output is correct
15 Correct 7 ms 31056 KB Output is correct
16 Correct 6 ms 24912 KB Output is correct
17 Correct 5 ms 24912 KB Output is correct
18 Correct 8 ms 24912 KB Output is correct
19 Correct 7 ms 24912 KB Output is correct
20 Correct 7 ms 24968 KB Output is correct
21 Correct 6 ms 25168 KB Output is correct
22 Correct 9 ms 25168 KB Output is correct
23 Correct 8 ms 24912 KB Output is correct
24 Correct 8 ms 25048 KB Output is correct
25 Correct 6 ms 25084 KB Output is correct
26 Runtime error 896 ms 262144 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31056 KB Output is correct
2 Correct 5 ms 31084 KB Output is correct
3 Correct 6 ms 31312 KB Output is correct
4 Correct 5 ms 31056 KB Output is correct
5 Correct 5 ms 31056 KB Output is correct
6 Correct 5 ms 31056 KB Output is correct
7 Correct 5 ms 31056 KB Output is correct
8 Correct 5 ms 31056 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 27092 KB Output is correct
12 Correct 8 ms 31056 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 10 ms 24912 KB Output is correct
15 Correct 7 ms 31056 KB Output is correct
16 Correct 6 ms 24912 KB Output is correct
17 Correct 5 ms 24912 KB Output is correct
18 Correct 8 ms 24912 KB Output is correct
19 Correct 7 ms 24912 KB Output is correct
20 Correct 7 ms 24968 KB Output is correct
21 Correct 6 ms 25168 KB Output is correct
22 Correct 9 ms 25168 KB Output is correct
23 Correct 8 ms 24912 KB Output is correct
24 Correct 8 ms 25048 KB Output is correct
25 Correct 6 ms 31056 KB Output is correct
26 Correct 88 ms 74472 KB Output is correct
27 Correct 97 ms 74312 KB Output is correct
28 Correct 7 ms 33784 KB Output is correct
29 Correct 6 ms 31056 KB Output is correct
30 Correct 9 ms 24912 KB Output is correct
31 Correct 93 ms 75336 KB Output is correct
32 Correct 6 ms 27472 KB Output is correct
33 Correct 113 ms 82300 KB Output is correct
34 Correct 103 ms 74396 KB Output is correct
35 Correct 11 ms 26448 KB Output is correct
36 Correct 120 ms 74500 KB Output is correct
37 Correct 8 ms 26616 KB Output is correct
38 Correct 7 ms 33616 KB Output is correct
39 Correct 89 ms 75656 KB Output is correct
40 Correct 10 ms 26704 KB Output is correct
41 Correct 75 ms 74072 KB Output is correct
42 Correct 105 ms 76608 KB Output is correct
43 Correct 5 ms 25168 KB Output is correct
44 Correct 86 ms 82620 KB Output is correct
45 Correct 121 ms 79556 KB Output is correct
46 Correct 7 ms 29520 KB Output is correct
47 Correct 12 ms 26376 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 72812 KB Output is correct
2 Execution timed out 3078 ms 62572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31056 KB Output is correct
2 Correct 5 ms 31084 KB Output is correct
3 Correct 6 ms 31312 KB Output is correct
4 Correct 5 ms 31056 KB Output is correct
5 Correct 5 ms 31056 KB Output is correct
6 Correct 5 ms 31056 KB Output is correct
7 Correct 5 ms 31056 KB Output is correct
8 Correct 5 ms 31056 KB Output is correct
9 Correct 4 ms 24912 KB Output is correct
10 Correct 5 ms 24912 KB Output is correct
11 Correct 5 ms 27092 KB Output is correct
12 Correct 8 ms 31056 KB Output is correct
13 Correct 5 ms 26960 KB Output is correct
14 Correct 10 ms 24912 KB Output is correct
15 Correct 7 ms 31056 KB Output is correct
16 Correct 6 ms 24912 KB Output is correct
17 Correct 5 ms 24912 KB Output is correct
18 Correct 8 ms 24912 KB Output is correct
19 Correct 7 ms 24912 KB Output is correct
20 Correct 7 ms 24968 KB Output is correct
21 Correct 6 ms 25168 KB Output is correct
22 Correct 9 ms 25168 KB Output is correct
23 Correct 8 ms 24912 KB Output is correct
24 Correct 8 ms 25048 KB Output is correct
25 Correct 6 ms 25084 KB Output is correct
26 Runtime error 896 ms 262144 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -