답안 #985275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
985275	2024-05-17T14:15:44 Z	alextodoran	수도 (JOI20_capital_city)	C++17	100 / 100	454 ms	42444 KB

capital_city

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

int N, K;
vector <int> adj[N_MAX + 2];
int C[N_MAX + 2];

bool erased[N_MAX + 2];

vector <int> nodes;
int parent[N_MAX + 2];
int sub[N_MAX + 2];
bool in_comp[N_MAX + 2];

vector <int> with_color[N_MAX + 2];

void dfs (int u, bool first) {
    if (first == true) {
        nodes.push_back(u);
        in_comp[u] = true;
    }
    sub[u] = 1;
    for (int v : adj[u]) {
        if (v != parent[u] && erased[v] == false) {
            parent[v] = u;
            dfs(v, first);
            sub[u] += sub[v];
        }
    }
}

int answer = INT_MAX / 2;
bool seen[N_MAX + 2];
bool cleared[N_MAX + 2];

void solve (int root) {
    parent[root] = 0; dfs(root, true);
    int centroid = 0;
    for (int u : nodes) {
        if (sub[root] - sub[u] > (int) nodes.size() / 2) {
            continue;
        }
        bool ok = true;
        for (int v : adj[u]) {
            if (v != parent[u] && erased[v] == false && sub[v] > (int) nodes.size() / 2) {
                ok = false;
                break;
            }
        }
        if (ok == true) {
            centroid = u;
            break;
        }
    }
    root = centroid;
    parent[root] = 0; dfs(root, false);
    queue <int> q;
    q.push(C[root]);
    cleared[C[root]] = true;
    int merges = 0;
    while (q.empty() == false) {
        int c = q.front(); q.pop();
        for (int u : with_color[c]) {
            if (in_comp[u] == false) {
                merges = INT_MAX / 2;
                break;
            }
            while (u != 0 && seen[u] == false) {
                if (cleared[C[u]] == false) {
                    cleared[C[u]] = true;
                    q.push(C[u]);
                    merges++;
                }
                seen[u] = true;
                u = parent[u];
            }
        }
    }
    answer = min(answer, merges);
    for (int u : nodes) {
        in_comp[u] = false;
        seen[u] = false;
        cleared[C[u]] = false;
    }
    nodes.clear();
    erased[root] = true;
    for (int u : adj[root]) {
        if (erased[u] == false) {
            solve(u);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int u = 1; u <= N; u++) {
        cin >> C[u];
        with_color[C[u]].push_back(u);
    }
    solve(1);
    cout << answer << "\n";

    return 0;
}

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12720 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	3 ms	12636 KB	Output is correct
6	Correct	3 ms	12772 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12776 KB	Output is correct
10	Correct	3 ms	12632 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12720 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	3 ms	12636 KB	Output is correct
6	Correct	3 ms	12772 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12776 KB	Output is correct
10	Correct	3 ms	12632 KB	Output is correct
11	Correct	4 ms	12888 KB	Output is correct
12	Correct	4 ms	12820 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Correct	4 ms	12936 KB	Output is correct
15	Correct	4 ms	12888 KB	Output is correct
16	Correct	4 ms	12888 KB	Output is correct
17	Correct	3 ms	12892 KB	Output is correct
18	Correct	3 ms	12892 KB	Output is correct
19	Correct	4 ms	12892 KB	Output is correct
20	Correct	4 ms	12884 KB	Output is correct
21	Correct	4 ms	12892 KB	Output is correct
22	Correct	4 ms	12932 KB	Output is correct
23	Correct	4 ms	12888 KB	Output is correct
24	Correct	3 ms	12892 KB	Output is correct
25	Correct	4 ms	12892 KB	Output is correct
26	Correct	4 ms	12892 KB	Output is correct
27	Correct	4 ms	12892 KB	Output is correct
28	Correct	4 ms	12892 KB	Output is correct
29	Correct	4 ms	12892 KB	Output is correct
30	Correct	4 ms	12892 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	353 ms	40660 KB	Output is correct
2	Correct	159 ms	40728 KB	Output is correct
3	Correct	353 ms	39884 KB	Output is correct
4	Correct	163 ms	40748 KB	Output is correct
5	Correct	335 ms	36896 KB	Output is correct
6	Correct	168 ms	40904 KB	Output is correct
7	Correct	329 ms	37396 KB	Output is correct
8	Correct	148 ms	40592 KB	Output is correct
9	Correct	370 ms	35524 KB	Output is correct
10	Correct	423 ms	33228 KB	Output is correct
11	Correct	392 ms	36036 KB	Output is correct
12	Correct	389 ms	38600 KB	Output is correct
13	Correct	454 ms	32876 KB	Output is correct
14	Correct	388 ms	39020 KB	Output is correct
15	Correct	388 ms	38600 KB	Output is correct
16	Correct	429 ms	33508 KB	Output is correct
17	Correct	393 ms	34180 KB	Output is correct
18	Correct	419 ms	34248 KB	Output is correct
19	Correct	426 ms	37572 KB	Output is correct
20	Correct	391 ms	39776 KB	Output is correct
21	Correct	3 ms	12636 KB	Output is correct

Subtask #4
59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12720 KB	Output is correct
2	Correct	2 ms	12636 KB	Output is correct
3	Correct	2 ms	12636 KB	Output is correct
4	Correct	2 ms	12636 KB	Output is correct
5	Correct	3 ms	12636 KB	Output is correct
6	Correct	3 ms	12772 KB	Output is correct
7	Correct	2 ms	12636 KB	Output is correct
8	Correct	2 ms	12636 KB	Output is correct
9	Correct	2 ms	12776 KB	Output is correct
10	Correct	3 ms	12632 KB	Output is correct
11	Correct	4 ms	12888 KB	Output is correct
12	Correct	4 ms	12820 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Correct	4 ms	12936 KB	Output is correct
15	Correct	4 ms	12888 KB	Output is correct
16	Correct	4 ms	12888 KB	Output is correct
17	Correct	3 ms	12892 KB	Output is correct
18	Correct	3 ms	12892 KB	Output is correct
19	Correct	4 ms	12892 KB	Output is correct
20	Correct	4 ms	12884 KB	Output is correct
21	Correct	4 ms	12892 KB	Output is correct
22	Correct	4 ms	12932 KB	Output is correct
23	Correct	4 ms	12888 KB	Output is correct
24	Correct	3 ms	12892 KB	Output is correct
25	Correct	4 ms	12892 KB	Output is correct
26	Correct	4 ms	12892 KB	Output is correct
27	Correct	4 ms	12892 KB	Output is correct
28	Correct	4 ms	12892 KB	Output is correct
29	Correct	4 ms	12892 KB	Output is correct
30	Correct	4 ms	12892 KB	Output is correct
31	Correct	353 ms	40660 KB	Output is correct
32	Correct	159 ms	40728 KB	Output is correct
33	Correct	353 ms	39884 KB	Output is correct
34	Correct	163 ms	40748 KB	Output is correct
35	Correct	335 ms	36896 KB	Output is correct
36	Correct	168 ms	40904 KB	Output is correct
37	Correct	329 ms	37396 KB	Output is correct
38	Correct	148 ms	40592 KB	Output is correct
39	Correct	370 ms	35524 KB	Output is correct
40	Correct	423 ms	33228 KB	Output is correct
41	Correct	392 ms	36036 KB	Output is correct
42	Correct	389 ms	38600 KB	Output is correct
43	Correct	454 ms	32876 KB	Output is correct
44	Correct	388 ms	39020 KB	Output is correct
45	Correct	388 ms	38600 KB	Output is correct
46	Correct	429 ms	33508 KB	Output is correct
47	Correct	393 ms	34180 KB	Output is correct
48	Correct	419 ms	34248 KB	Output is correct
49	Correct	426 ms	37572 KB	Output is correct
50	Correct	391 ms	39776 KB	Output is correct
51	Correct	3 ms	12636 KB	Output is correct
52	Correct	319 ms	24028 KB	Output is correct
53	Correct	259 ms	23932 KB	Output is correct
54	Correct	258 ms	23860 KB	Output is correct
55	Correct	329 ms	24012 KB	Output is correct
56	Correct	273 ms	24012 KB	Output is correct
57	Correct	263 ms	24012 KB	Output is correct
58	Correct	247 ms	27132 KB	Output is correct
59	Correct	255 ms	27852 KB	Output is correct
60	Correct	356 ms	27084 KB	Output is correct
61	Correct	326 ms	26632 KB	Output is correct
62	Correct	152 ms	42392 KB	Output is correct
63	Correct	157 ms	42444 KB	Output is correct
64	Correct	154 ms	42056 KB	Output is correct
65	Correct	153 ms	42404 KB	Output is correct
66	Correct	201 ms	34164 KB	Output is correct
67	Correct	216 ms	33796 KB	Output is correct
68	Correct	229 ms	34092 KB	Output is correct
69	Correct	223 ms	34440 KB	Output is correct
70	Correct	200 ms	33932 KB	Output is correct
71	Correct	224 ms	34024 KB	Output is correct
72	Correct	204 ms	33964 KB	Output is correct
73	Correct	212 ms	33164 KB	Output is correct
74	Correct	196 ms	34184 KB	Output is correct
75	Correct	210 ms	34184 KB	Output is correct
76	Correct	294 ms	32596 KB	Output is correct
77	Correct	323 ms	30664 KB	Output is correct
78	Correct	381 ms	36036 KB	Output is correct
79	Correct	376 ms	33856 KB	Output is correct
80	Correct	381 ms	40904 KB	Output is correct
81	Correct	381 ms	37336 KB	Output is correct
82	Correct	386 ms	37380 KB	Output is correct
83	Correct	386 ms	34248 KB	Output is correct
84	Correct	390 ms	39876 KB	Output is correct
85	Correct	400 ms	38388 KB	Output is correct
86	Correct	381 ms	33740 KB	Output is correct
87	Correct	392 ms	35640 KB	Output is correct
88	Correct	316 ms	36504 KB	Output is correct
89	Correct	326 ms	32756 KB	Output is correct
90	Correct	310 ms	32456 KB	Output is correct
91	Correct	323 ms	34904 KB	Output is correct
92	Correct	338 ms	33440 KB	Output is correct
93	Correct	325 ms	32972 KB	Output is correct
94	Correct	315 ms	32456 KB	Output is correct
95	Correct	320 ms	34172 KB	Output is correct
96	Correct	326 ms	33004 KB	Output is correct
97	Correct	321 ms	34712 KB	Output is correct

답안 #985275

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