oj.uz

Submission #1116879

# Submission time Handle Problem Language Result Execution time Memory
1116879 2024-11-22T13:58:39 Z vjudge1 Mergers (JOI19_mergers) C++17
48 / 100
 3000 ms 79472 KB 
#include <bits/stdc++.h>
#define int long long
#define double long double
#define arr2 array<int, 2>
#define popcount __builtin_popcountll
#define ctz __builtin_ctzll
#define arr3 array<int, 3>

using namespace std;

const int N = 5e5 + 10, M = 1e9 + 7;

vector<int> adj[N];
int n, k;
int col[N];
int cnt[N];
int ths[N];
int par[N];
int sz[N];
int cnt1[N];
vector<arr2> cut;
stack<vector<int>> stk;

void crt(int a) {
    par[a] = a;
    sz[a] = 1;
}

int get(int a) {
    return (a == par[a] ? a : (par[a] = get(par[a])));
}

void mrg(int a, int b) {
    a = get(a), b = get(b);
    if (a == b) {
        return;
    }
    if (sz[a] > sz[b]) {
        swap(a, b);
    }
    par[a] = b;
    sz[b] = sz[a] + sz[b];
}

bool same(int a, int b) {
    return get(a) == get(b);
}

void dfs(int a, int b = 0) {
    stk.push(vector<int>(k + 1));
    for (int i = 0; i <= k; ++i) {
        stk.top()[i] = ths[i];
    }
    ths[col[a]]++;
    for (int i : adj[a]) {
        if (i != b) {
            dfs(i, a);
        }
    }
    if (a == 1) {
        return;
    }
    for (int i = 0; i <= k; ++i) {
        if ((ths[i] - stk.top()[i] != 0) and (ths[i] - stk.top()[i] != cnt[i])) {
            mrg(a, b);
            stk.pop();
            return;
        }
    }
    cut.push_back({a, b});
    stk.pop();
}

void fun() {
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        col[i] = a;
        cnt[a]++;
        crt(i);
    }
    dfs(1);
    for (arr2 i : cut) {
        cnt1[get(i[0])]++, cnt1[get(i[1])]++;
    }
    int c = 0;
    for (int i = 1; i <= n; ++i) {
        if (cnt1[i] == 1) {
            c++;
        }
    }
    cout << (c + 1) / 2 << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // int tc;
    // cin >> tc;
    // while (tc--)
    fun();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21072 KB Output is correct
2 Correct 3 ms 21072 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 20932 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 3 ms 21072 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 4 ms 21144 KB Output is correct
12 Correct 4 ms 21240 KB Output is correct
13 Correct 3 ms 21072 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 3 ms 19024 KB Output is correct
16 Correct 4 ms 21072 KB Output is correct
17 Correct 4 ms 21072 KB Output is correct
18 Correct 4 ms 19024 KB Output is correct
19 Correct 3 ms 19192 KB Output is correct
20 Correct 3 ms 21072 KB Output is correct
21 Correct 3 ms 21072 KB Output is correct
22 Correct 4 ms 21072 KB Output is correct
23 Correct 4 ms 21244 KB Output is correct
24 Correct 3 ms 21072 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21072 KB Output is correct
2 Correct 3 ms 21072 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 20932 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 3 ms 21072 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 4 ms 21144 KB Output is correct
12 Correct 4 ms 21240 KB Output is correct
13 Correct 3 ms 21072 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 3 ms 19024 KB Output is correct
16 Correct 4 ms 21072 KB Output is correct
17 Correct 4 ms 21072 KB Output is correct
18 Correct 4 ms 19024 KB Output is correct
19 Correct 3 ms 19192 KB Output is correct
20 Correct 3 ms 21072 KB Output is correct
21 Correct 3 ms 21072 KB Output is correct
22 Correct 4 ms 21072 KB Output is correct
23 Correct 4 ms 21244 KB Output is correct
24 Correct 3 ms 21072 KB Output is correct
25 Correct 4 ms 21072 KB Output is correct
26 Correct 16 ms 22032 KB Output is correct
27 Correct 6 ms 21456 KB Output is correct
28 Correct 46 ms 54864 KB Output is correct
29 Correct 24 ms 21888 KB Output is correct
30 Correct 6 ms 21148 KB Output is correct
31 Correct 6 ms 21140 KB Output is correct
32 Correct 54 ms 72760 KB Output is correct
33 Correct 4 ms 21072 KB Output is correct
34 Correct 4 ms 21072 KB Output is correct
35 Correct 22 ms 21992 KB Output is correct
36 Correct 5 ms 21328 KB Output is correct
37 Correct 12 ms 22012 KB Output is correct
38 Correct 4 ms 21072 KB Output is correct
39 Correct 11 ms 21536 KB Output is correct
40 Correct 4 ms 21072 KB Output is correct
41 Correct 5 ms 21328 KB Output is correct
42 Correct 11 ms 21324 KB Output is correct
43 Correct 5 ms 21584 KB Output is correct
44 Correct 4 ms 21072 KB Output is correct
45 Correct 28 ms 35920 KB Output is correct
46 Correct 15 ms 20324 KB Output is correct
47 Correct 4 ms 21072 KB Output is correct
48 Correct 9 ms 21648 KB Output is correct
49 Correct 27 ms 19528 KB Output is correct
50 Correct 36 ms 39760 KB Output is correct
51 Correct 9 ms 21588 KB Output is correct
52 Correct 5 ms 21496 KB Output is correct
53 Correct 11 ms 21500 KB Output is correct
54 Correct 5 ms 21072 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21072 KB Output is correct
2 Correct 3 ms 21072 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 20932 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 3 ms 21072 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 4 ms 21144 KB Output is correct
12 Correct 4 ms 21240 KB Output is correct
13 Correct 3 ms 21072 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 3 ms 19024 KB Output is correct
16 Correct 4 ms 21072 KB Output is correct
17 Correct 4 ms 21072 KB Output is correct
18 Correct 4 ms 19024 KB Output is correct
19 Correct 3 ms 19192 KB Output is correct
20 Correct 3 ms 21072 KB Output is correct
21 Correct 3 ms 21072 KB Output is correct
22 Correct 4 ms 21072 KB Output is correct
23 Correct 4 ms 21244 KB Output is correct
24 Correct 3 ms 21072 KB Output is correct
25 Correct 4 ms 21328 KB Output is correct
26 Correct 39 ms 27124 KB Output is correct
27 Correct 56 ms 27988 KB Output is correct
28 Correct 5 ms 19280 KB Output is correct
29 Correct 4 ms 21072 KB Output is correct
30 Correct 3 ms 21072 KB Output is correct
31 Correct 47 ms 32072 KB Output is correct
32 Correct 5 ms 21072 KB Output is correct
33 Correct 87 ms 79472 KB Output is correct
34 Correct 62 ms 31876 KB Output is correct
35 Correct 7 ms 21328 KB Output is correct
36 Correct 77 ms 35636 KB Output is correct
37 Correct 4 ms 21072 KB Output is correct
38 Correct 5 ms 17232 KB Output is correct
39 Correct 37 ms 28992 KB Output is correct
40 Correct 5 ms 21584 KB Output is correct
41 Correct 38 ms 27192 KB Output is correct
42 Correct 82 ms 46156 KB Output is correct
43 Correct 3 ms 21072 KB Output is correct
44 Correct 55 ms 41800 KB Output is correct
45 Correct 77 ms 53576 KB Output is correct
46 Correct 5 ms 21328 KB Output is correct
47 Correct 5 ms 19280 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 25540 KB Output is correct
2 Execution timed out 3065 ms 33220 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21072 KB Output is correct
2 Correct 3 ms 21072 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 20932 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 3 ms 21072 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 4 ms 21072 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 4 ms 21144 KB Output is correct
12 Correct 4 ms 21240 KB Output is correct
13 Correct 3 ms 21072 KB Output is correct
14 Correct 3 ms 19024 KB Output is correct
15 Correct 3 ms 19024 KB Output is correct
16 Correct 4 ms 21072 KB Output is correct
17 Correct 4 ms 21072 KB Output is correct
18 Correct 4 ms 19024 KB Output is correct
19 Correct 3 ms 19192 KB Output is correct
20 Correct 3 ms 21072 KB Output is correct
21 Correct 3 ms 21072 KB Output is correct
22 Correct 4 ms 21072 KB Output is correct
23 Correct 4 ms 21244 KB Output is correct
24 Correct 3 ms 21072 KB Output is correct
25 Correct 4 ms 21072 KB Output is correct
26 Correct 16 ms 22032 KB Output is correct
27 Correct 6 ms 21456 KB Output is correct
28 Correct 46 ms 54864 KB Output is correct
29 Correct 24 ms 21888 KB Output is correct
30 Correct 6 ms 21148 KB Output is correct
31 Correct 6 ms 21140 KB Output is correct
32 Correct 54 ms 72760 KB Output is correct
33 Correct 4 ms 21072 KB Output is correct
34 Correct 4 ms 21072 KB Output is correct
35 Correct 22 ms 21992 KB Output is correct
36 Correct 5 ms 21328 KB Output is correct
37 Correct 12 ms 22012 KB Output is correct
38 Correct 4 ms 21072 KB Output is correct
39 Correct 11 ms 21536 KB Output is correct
40 Correct 4 ms 21072 KB Output is correct
41 Correct 5 ms 21328 KB Output is correct
42 Correct 11 ms 21324 KB Output is correct
43 Correct 5 ms 21584 KB Output is correct
44 Correct 4 ms 21072 KB Output is correct
45 Correct 28 ms 35920 KB Output is correct
46 Correct 15 ms 20324 KB Output is correct
47 Correct 4 ms 21072 KB Output is correct
48 Correct 9 ms 21648 KB Output is correct
49 Correct 27 ms 19528 KB Output is correct
50 Correct 36 ms 39760 KB Output is correct
51 Correct 9 ms 21588 KB Output is correct
52 Correct 5 ms 21496 KB Output is correct
53 Correct 11 ms 21500 KB Output is correct
54 Correct 5 ms 21072 KB Output is correct
55 Correct 4 ms 21328 KB Output is correct
56 Correct 39 ms 27124 KB Output is correct
57 Correct 56 ms 27988 KB Output is correct
58 Correct 5 ms 19280 KB Output is correct
59 Correct 4 ms 21072 KB Output is correct
60 Correct 3 ms 21072 KB Output is correct
61 Correct 47 ms 32072 KB Output is correct
62 Correct 5 ms 21072 KB Output is correct
63 Correct 87 ms 79472 KB Output is correct
64 Correct 62 ms 31876 KB Output is correct
65 Correct 7 ms 21328 KB Output is correct
66 Correct 77 ms 35636 KB Output is correct
67 Correct 4 ms 21072 KB Output is correct
68 Correct 5 ms 17232 KB Output is correct
69 Correct 37 ms 28992 KB Output is correct
70 Correct 5 ms 21584 KB Output is correct
71 Correct 38 ms 27192 KB Output is correct
72 Correct 82 ms 46156 KB Output is correct
73 Correct 3 ms 21072 KB Output is correct
74 Correct 55 ms 41800 KB Output is correct
75 Correct 77 ms 53576 KB Output is correct
76 Correct 5 ms 21328 KB Output is correct
77 Correct 5 ms 19280 KB Output is correct
78 Correct 37 ms 25540 KB Output is correct
79 Execution timed out 3065 ms 33220 KB Time limit exceeded
80 Halted 0 ms 0 KB -