Submission #540279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
540279	2022-03-19T19:52:31 Z	surgutti	Capital City (JOI20_capital_city)	C++17	100 / 100	1168 ms	49820 KB

capital_city

#include <bits/stdc++.h>

using namespace std;

const int N = 200'007;

int n, k;
vector<int> adj[N];
int c[N];

vector<int> col[N];
int vis[N], sz[N], par[N], done[N], tim;
vector<int> cur[N];

void prepare(int u, int f) {
    sz[u] = 1;
    cur[c[u]].push_back(u);
    for (int v : adj[u]) if (!vis[v] && v != f) {
        prepare(v, u);
        sz[u] += sz[v];
        par[v] = u;
    }
}

int find_centroid(int u, int f, int all) {
    for (int v : adj[u]) if (!vis[v] && v != f) {
        if (sz[v] >= all / 2) {
            return find_centroid(v, u, all);
        }
    }
    return u;
}

void clear(int u, int f) {
    cur[c[u]].clear();
    for (int v : adj[u]) if (!vis[v] && v != f) {
        clear(v, u);
    }
}

int ans = N;

void solve(int u) {

    prepare(u, u);

    int centroid = find_centroid(u, u, sz[u]);

    clear(u, u);

    prepare(centroid, centroid);

    queue<int> q;
    q.push(c[centroid]);

    ++tim;

    done[c[centroid]] = tim;

    int now = 0;
    while (q.size()) {
        int v = q.front(); q.pop();
        now++;

        if (cur[v].size() != col[v].size()) {
            now = N;
            break;
        }

        for (int w : cur[v]) if (w != centroid) {
            w = par[w];
            if (done[c[w]] != tim) {
                done[c[w]] = tim;
                q.push(c[w]);
            }
        }
    }
   
    ans = min(ans, now - 1);

    clear(centroid, centroid);

    vis[centroid] = true;

    for (int v : adj[centroid]) if (!vis[v]) {
        solve(v);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--, v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 0; i < n; i++) {
        cin >> c[i]; c[i]--;
        col[c[i]].push_back(i);
    }

    solve(0);

    cout << ans << '\n';
}

Subtask #1
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	7 ms	14400 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14436 KB	Output is correct
9	Correct	7 ms	14420 KB	Output is correct
10	Correct	8 ms	14356 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	7 ms	14400 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14436 KB	Output is correct
9	Correct	7 ms	14420 KB	Output is correct
10	Correct	8 ms	14356 KB	Output is correct
11	Correct	9 ms	14576 KB	Output is correct
12	Correct	10 ms	14576 KB	Output is correct
13	Correct	10 ms	14580 KB	Output is correct
14	Correct	10 ms	14548 KB	Output is correct
15	Correct	9 ms	14620 KB	Output is correct
16	Correct	10 ms	14548 KB	Output is correct
17	Correct	9 ms	14676 KB	Output is correct
18	Correct	9 ms	14616 KB	Output is correct
19	Correct	8 ms	14676 KB	Output is correct
20	Correct	9 ms	14676 KB	Output is correct
21	Correct	9 ms	14676 KB	Output is correct
22	Correct	11 ms	14720 KB	Output is correct
23	Correct	10 ms	14712 KB	Output is correct
24	Correct	12 ms	14576 KB	Output is correct
25	Correct	10 ms	14628 KB	Output is correct
26	Correct	10 ms	14700 KB	Output is correct
27	Correct	11 ms	14676 KB	Output is correct
28	Correct	11 ms	14676 KB	Output is correct
29	Correct	11 ms	14620 KB	Output is correct
30	Correct	10 ms	14624 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1053 ms	45604 KB	Output is correct
2	Correct	296 ms	49796 KB	Output is correct
3	Correct	1104 ms	48948 KB	Output is correct
4	Correct	296 ms	49720 KB	Output is correct
5	Correct	1043 ms	45900 KB	Output is correct
6	Correct	300 ms	49604 KB	Output is correct
7	Correct	965 ms	46044 KB	Output is correct
8	Correct	294 ms	48904 KB	Output is correct
9	Correct	1004 ms	43368 KB	Output is correct
10	Correct	1028 ms	40896 KB	Output is correct
11	Correct	1014 ms	43808 KB	Output is correct
12	Correct	1002 ms	46332 KB	Output is correct
13	Correct	1012 ms	40344 KB	Output is correct
14	Correct	1014 ms	46668 KB	Output is correct
15	Correct	1059 ms	46352 KB	Output is correct
16	Correct	980 ms	41528 KB	Output is correct
17	Correct	1004 ms	41924 KB	Output is correct
18	Correct	1008 ms	42132 KB	Output is correct
19	Correct	1000 ms	45388 KB	Output is correct
20	Correct	1014 ms	47448 KB	Output is correct
21	Correct	8 ms	14420 KB	Output is correct

Subtask #4
59.0 / 59.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	7 ms	14400 KB	Output is correct
3	Correct	8 ms	14388 KB	Output is correct
4	Correct	7 ms	14420 KB	Output is correct
5	Correct	8 ms	14420 KB	Output is correct
6	Correct	7 ms	14420 KB	Output is correct
7	Correct	8 ms	14420 KB	Output is correct
8	Correct	8 ms	14436 KB	Output is correct
9	Correct	7 ms	14420 KB	Output is correct
10	Correct	8 ms	14356 KB	Output is correct
11	Correct	9 ms	14576 KB	Output is correct
12	Correct	10 ms	14576 KB	Output is correct
13	Correct	10 ms	14580 KB	Output is correct
14	Correct	10 ms	14548 KB	Output is correct
15	Correct	9 ms	14620 KB	Output is correct
16	Correct	10 ms	14548 KB	Output is correct
17	Correct	9 ms	14676 KB	Output is correct
18	Correct	9 ms	14616 KB	Output is correct
19	Correct	8 ms	14676 KB	Output is correct
20	Correct	9 ms	14676 KB	Output is correct
21	Correct	9 ms	14676 KB	Output is correct
22	Correct	11 ms	14720 KB	Output is correct
23	Correct	10 ms	14712 KB	Output is correct
24	Correct	12 ms	14576 KB	Output is correct
25	Correct	10 ms	14628 KB	Output is correct
26	Correct	10 ms	14700 KB	Output is correct
27	Correct	11 ms	14676 KB	Output is correct
28	Correct	11 ms	14676 KB	Output is correct
29	Correct	11 ms	14620 KB	Output is correct
30	Correct	10 ms	14624 KB	Output is correct
31	Correct	1053 ms	45604 KB	Output is correct
32	Correct	296 ms	49796 KB	Output is correct
33	Correct	1104 ms	48948 KB	Output is correct
34	Correct	296 ms	49720 KB	Output is correct
35	Correct	1043 ms	45900 KB	Output is correct
36	Correct	300 ms	49604 KB	Output is correct
37	Correct	965 ms	46044 KB	Output is correct
38	Correct	294 ms	48904 KB	Output is correct
39	Correct	1004 ms	43368 KB	Output is correct
40	Correct	1028 ms	40896 KB	Output is correct
41	Correct	1014 ms	43808 KB	Output is correct
42	Correct	1002 ms	46332 KB	Output is correct
43	Correct	1012 ms	40344 KB	Output is correct
44	Correct	1014 ms	46668 KB	Output is correct
45	Correct	1059 ms	46352 KB	Output is correct
46	Correct	980 ms	41528 KB	Output is correct
47	Correct	1004 ms	41924 KB	Output is correct
48	Correct	1008 ms	42132 KB	Output is correct
49	Correct	1000 ms	45388 KB	Output is correct
50	Correct	1014 ms	47448 KB	Output is correct
51	Correct	8 ms	14420 KB	Output is correct
52	Correct	648 ms	30748 KB	Output is correct
53	Correct	687 ms	30648 KB	Output is correct
54	Correct	728 ms	30612 KB	Output is correct
55	Correct	742 ms	30660 KB	Output is correct
56	Correct	710 ms	30648 KB	Output is correct
57	Correct	681 ms	30668 KB	Output is correct
58	Correct	666 ms	35496 KB	Output is correct
59	Correct	698 ms	35788 KB	Output is correct
60	Correct	988 ms	35436 KB	Output is correct
61	Correct	919 ms	35132 KB	Output is correct
62	Correct	295 ms	49784 KB	Output is correct
63	Correct	293 ms	49820 KB	Output is correct
64	Correct	290 ms	49152 KB	Output is correct
65	Correct	290 ms	49596 KB	Output is correct
66	Correct	477 ms	40068 KB	Output is correct
67	Correct	465 ms	39768 KB	Output is correct
68	Correct	500 ms	39912 KB	Output is correct
69	Correct	483 ms	39888 KB	Output is correct
70	Correct	533 ms	39796 KB	Output is correct
71	Correct	484 ms	39792 KB	Output is correct
72	Correct	504 ms	39684 KB	Output is correct
73	Correct	475 ms	38968 KB	Output is correct
74	Correct	481 ms	39812 KB	Output is correct
75	Correct	479 ms	39800 KB	Output is correct
76	Correct	774 ms	39928 KB	Output is correct
77	Correct	816 ms	38060 KB	Output is correct
78	Correct	973 ms	41992 KB	Output is correct
79	Correct	976 ms	40012 KB	Output is correct
80	Correct	962 ms	46864 KB	Output is correct
81	Correct	1004 ms	43448 KB	Output is correct
82	Correct	1010 ms	43652 KB	Output is correct
83	Correct	1030 ms	40196 KB	Output is correct
84	Correct	1025 ms	46120 KB	Output is correct
85	Correct	1036 ms	44500 KB	Output is correct
86	Correct	1154 ms	39868 KB	Output is correct
87	Correct	1168 ms	41536 KB	Output is correct
88	Correct	1049 ms	42684 KB	Output is correct
89	Correct	1100 ms	38644 KB	Output is correct
90	Correct	902 ms	38444 KB	Output is correct
91	Correct	944 ms	40828 KB	Output is correct
92	Correct	948 ms	39460 KB	Output is correct
93	Correct	917 ms	39268 KB	Output is correct
94	Correct	1076 ms	38568 KB	Output is correct
95	Correct	866 ms	40168 KB	Output is correct
96	Correct	873 ms	38804 KB	Output is correct
97	Correct	866 ms	40848 KB	Output is correct

Submission #540279

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 10.0 / 10.0

Subtask #3 30.0 / 30.0

Subtask #4 59.0 / 59.0

Subtask #1
1.0 / 1.0

Subtask #2
10.0 / 10.0

Subtask #3
30.0 / 30.0

Subtask #4
59.0 / 59.0