답안 #928347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928347	2024-02-16T08:47:38 Z	Amirreza_Fakhri	수도 (JOI20_capital_city)	C++17	100 / 100	374 ms	38904 KB

capital_city

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5;

int n, k, c[maxn], sz[maxn], par[maxn], id[maxn];
bool mark[maxn], vis[maxn];
vector <int> adj[maxn], vec[maxn];
queue <int> q;

void dfs1(int v, int p) {
    sz[v] = 1;
    vis[c[v]] = 1;
    for (int u : adj[v]) {
        if (!mark[u] and u != p) {
            dfs1(u, v); sz[v] += sz[u];
        }
    }
}

void dfs2(int v, int p, int r) {
    par[v] = p, id[v] = r;
    for (int u : adj[v]) {
        if (!mark[u] and u != p) dfs2(u, v, r);
    }
}

int fcen(int v, int p, int s) {
    for (int u : adj[v]) {
        if (!mark[u] and u != p and sz[u]*2 > s) return fcen(u, v, s);
    }
    return v;
}

int cen(int v) {
    dfs1(v, v);
    v = fcen(v, v, sz[v]);
    dfs2(v, v, v); 
    int ans = 0;
    q.push(c[v]);
    while (q.size()) {
        int col = q.front(); q.pop();
        if (!vis[col]) continue;
        vis[col] = 0;
        for (int u : vec[col]) {
            if (id[u] != v) {
                ans = k; break;
            }
            q.push(c[par[u]]);
        }
        ans++;
    }
    mark[v] = 1;
    for (int u : adj[v]) {
        if (!mark[u]) smin(ans, cen(u));
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int v, u; cin >> v >> u;
        adj[--v].pb(--u);
        adj[u].pb(v);
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i]; vec[--c[i]].pb(i);
    }
    cout << cen(0)-1 << '\n';
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	330 ms	34864 KB	Output is correct
2	Correct	128 ms	38740 KB	Output is correct
3	Correct	345 ms	38276 KB	Output is correct
4	Correct	134 ms	38740 KB	Output is correct
5	Correct	289 ms	35812 KB	Output is correct
6	Correct	128 ms	38904 KB	Output is correct
7	Correct	318 ms	35920 KB	Output is correct
8	Correct	127 ms	38464 KB	Output is correct
9	Correct	330 ms	34644 KB	Output is correct
10	Correct	295 ms	32668 KB	Output is correct
11	Correct	315 ms	35232 KB	Output is correct
12	Correct	345 ms	37132 KB	Output is correct
13	Correct	356 ms	32504 KB	Output is correct
14	Correct	355 ms	37456 KB	Output is correct
15	Correct	370 ms	37304 KB	Output is correct
16	Correct	317 ms	33092 KB	Output is correct
17	Correct	367 ms	33620 KB	Output is correct
18	Correct	318 ms	33548 KB	Output is correct
19	Correct	326 ms	36436 KB	Output is correct
20	Correct	374 ms	37980 KB	Output is correct
21	Correct	3 ms	12888 KB	Output is correct

Subtask #4
59.0 / 59.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12888 KB	Output is correct
2	Correct	2 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	2 ms	12892 KB	Output is correct
5	Correct	2 ms	12892 KB	Output is correct
6	Correct	2 ms	12892 KB	Output is correct
7	Correct	2 ms	12892 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	2 ms	12888 KB	Output is correct
10	Correct	2 ms	12892 KB	Output is correct
11	Correct	3 ms	12888 KB	Output is correct
12	Correct	5 ms	12892 KB	Output is correct
13	Correct	3 ms	12888 KB	Output is correct
14	Correct	4 ms	12888 KB	Output is correct
15	Correct	3 ms	12892 KB	Output is correct
16	Correct	3 ms	12892 KB	Output is correct
17	Correct	3 ms	12892 KB	Output is correct
18	Correct	3 ms	12888 KB	Output is correct
19	Correct	3 ms	12888 KB	Output is correct
20	Correct	4 ms	12888 KB	Output is correct
21	Correct	3 ms	12888 KB	Output is correct
22	Correct	4 ms	13148 KB	Output is correct
23	Correct	3 ms	12892 KB	Output is correct
24	Correct	4 ms	12888 KB	Output is correct
25	Correct	5 ms	12892 KB	Output is correct
26	Correct	4 ms	12984 KB	Output is correct
27	Correct	4 ms	12888 KB	Output is correct
28	Correct	4 ms	12892 KB	Output is correct
29	Correct	4 ms	12892 KB	Output is correct
30	Correct	3 ms	12892 KB	Output is correct
31	Correct	330 ms	34864 KB	Output is correct
32	Correct	128 ms	38740 KB	Output is correct
33	Correct	345 ms	38276 KB	Output is correct
34	Correct	134 ms	38740 KB	Output is correct
35	Correct	289 ms	35812 KB	Output is correct
36	Correct	128 ms	38904 KB	Output is correct
37	Correct	318 ms	35920 KB	Output is correct
38	Correct	127 ms	38464 KB	Output is correct
39	Correct	330 ms	34644 KB	Output is correct
40	Correct	295 ms	32668 KB	Output is correct
41	Correct	315 ms	35232 KB	Output is correct
42	Correct	345 ms	37132 KB	Output is correct
43	Correct	356 ms	32504 KB	Output is correct
44	Correct	355 ms	37456 KB	Output is correct
45	Correct	370 ms	37304 KB	Output is correct
46	Correct	317 ms	33092 KB	Output is correct
47	Correct	367 ms	33620 KB	Output is correct
48	Correct	318 ms	33548 KB	Output is correct
49	Correct	326 ms	36436 KB	Output is correct
50	Correct	374 ms	37980 KB	Output is correct
51	Correct	3 ms	12888 KB	Output is correct
52	Correct	198 ms	25244 KB	Output is correct
53	Correct	284 ms	25332 KB	Output is correct
54	Correct	226 ms	25428 KB	Output is correct
55	Correct	199 ms	25408 KB	Output is correct
56	Correct	209 ms	25172 KB	Output is correct
57	Correct	267 ms	25476 KB	Output is correct
58	Correct	207 ms	27976 KB	Output is correct
59	Correct	210 ms	28244 KB	Output is correct
60	Correct	238 ms	27896 KB	Output is correct
61	Correct	289 ms	27508 KB	Output is correct
62	Correct	127 ms	38716 KB	Output is correct
63	Correct	139 ms	38740 KB	Output is correct
64	Correct	130 ms	38752 KB	Output is correct
65	Correct	151 ms	38824 KB	Output is correct
66	Correct	193 ms	32452 KB	Output is correct
67	Correct	170 ms	32116 KB	Output is correct
68	Correct	172 ms	32200 KB	Output is correct
69	Correct	189 ms	32380 KB	Output is correct
70	Correct	191 ms	32200 KB	Output is correct
71	Correct	156 ms	32204 KB	Output is correct
72	Correct	169 ms	32204 KB	Output is correct
73	Correct	190 ms	31648 KB	Output is correct
74	Correct	172 ms	32196 KB	Output is correct
75	Correct	166 ms	32336 KB	Output is correct
76	Correct	241 ms	30780 KB	Output is correct
77	Correct	228 ms	29348 KB	Output is correct
78	Correct	324 ms	33500 KB	Output is correct
79	Correct	305 ms	31820 KB	Output is correct
80	Correct	315 ms	37716 KB	Output is correct
81	Correct	321 ms	34640 KB	Output is correct
82	Correct	305 ms	34896 KB	Output is correct
83	Correct	350 ms	32436 KB	Output is correct
84	Correct	298 ms	36688 KB	Output is correct
85	Correct	337 ms	35632 KB	Output is correct
86	Correct	304 ms	31824 KB	Output is correct
87	Correct	316 ms	33360 KB	Output is correct
88	Correct	248 ms	34132 KB	Output is correct
89	Correct	345 ms	31060 KB	Output is correct
90	Correct	303 ms	30952 KB	Output is correct
91	Correct	305 ms	32848 KB	Output is correct
92	Correct	263 ms	31576 KB	Output is correct
93	Correct	266 ms	31316 KB	Output is correct
94	Correct	274 ms	30984 KB	Output is correct
95	Correct	328 ms	32132 KB	Output is correct
96	Correct	265 ms	30976 KB	Output is correct
97	Correct	246 ms	32508 KB	Output is correct

답안 #928347

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