# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
315353 | 2020-10-22T15:10:03 Z | georgerapeanu | Capital City (JOI20_capital_city) | C++11 | 3000 ms | 42488 KB |
#include <bits/stdc++.h> using namespace std; const int NMAX = 200000; int n,k; int color[NMAX + 5]; vector<int> nodes[NMAX + 5]; vector<int> graph[NMAX + 5]; bool inCentroid[NMAX + 5]; int weight[NMAX + 5]; int father[NMAX + 5]; bool viz[NMAX + 5]; int group[NMAX + 5]; int processed[NMAX + 5]; int global_ans = 1e9; void predfs(int nod,int tata,int centroid){ weight[nod] = 1; processed[color[nod]] = false; viz[nod] = 0; group[nod] = centroid; father[nod] = tata; for(auto it:graph[nod]){ if(it == tata || inCentroid[nod]){ continue; } predfs(it,nod,centroid); weight[nod] += weight[it]; } } void dfs(int nod){ int _father = 0; int centroid = nod; while(true){ int bigChild = -1; for(auto it:graph[centroid]){ if(it == _father || inCentroid[it]){ continue; } if(bigChild == -1 || weight[bigChild] < weight[it]){ bigChild = it; } } if(weight[bigChild] * 2 > weight[nod]){ _father = centroid; centroid = bigChild; } else{ break; } } predfs(centroid,0,centroid); vector<int> colors = {color[centroid]}; inCentroid[centroid] = true; int ans = -1; processed[colors.back()] = true; while(colors.size()){ ans++; int col = colors.back(); colors.pop_back(); for(auto it:nodes[col]){ if(group[it] != centroid){ ans = 1e9; break; } int nod = it; while(nod && viz[nod] == 0){ viz[nod] = 1; if(processed[color[nod]] == 0){ colors.push_back(color[nod]); processed[color[nod]] = true; } nod = father[nod]; } } if(ans == 1e9){ break; } } global_ans = min(global_ans,ans); for(auto it:graph[centroid]){ if(inCentroid[it] == 0){ dfs(it); } } } int main(){ scanf("%d %d",&n,&k); for(int i = 1;i < n;i++){ int x,y; scanf("%d %d",&x,&y); graph[x].push_back(y); graph[y].push_back(x); } for(int i = 1;i <= n;i++){ scanf("%d",&color[i]); nodes[color[i]].push_back(i); } predfs(1,0,0); dfs(1); printf("%d\n",global_ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 9728 KB | Output is correct |
2 | Correct | 7 ms | 9728 KB | Output is correct |
3 | Correct | 7 ms | 9728 KB | Output is correct |
4 | Correct | 7 ms | 9728 KB | Output is correct |
5 | Correct | 7 ms | 9728 KB | Output is correct |
6 | Correct | 7 ms | 9728 KB | Output is correct |
7 | Correct | 7 ms | 9728 KB | Output is correct |
8 | Correct | 7 ms | 9728 KB | Output is correct |
9 | Correct | 7 ms | 9728 KB | Output is correct |
10 | Correct | 8 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 9728 KB | Output is correct |
2 | Correct | 7 ms | 9728 KB | Output is correct |
3 | Correct | 7 ms | 9728 KB | Output is correct |
4 | Correct | 7 ms | 9728 KB | Output is correct |
5 | Correct | 7 ms | 9728 KB | Output is correct |
6 | Correct | 7 ms | 9728 KB | Output is correct |
7 | Correct | 7 ms | 9728 KB | Output is correct |
8 | Correct | 7 ms | 9728 KB | Output is correct |
9 | Correct | 7 ms | 9728 KB | Output is correct |
10 | Correct | 8 ms | 9728 KB | Output is correct |
11 | Correct | 9 ms | 9888 KB | Output is correct |
12 | Correct | 9 ms | 9856 KB | Output is correct |
13 | Correct | 9 ms | 9856 KB | Output is correct |
14 | Correct | 9 ms | 9856 KB | Output is correct |
15 | Correct | 9 ms | 9984 KB | Output is correct |
16 | Correct | 9 ms | 9984 KB | Output is correct |
17 | Correct | 10 ms | 9984 KB | Output is correct |
18 | Correct | 10 ms | 10112 KB | Output is correct |
19 | Correct | 9 ms | 9984 KB | Output is correct |
20 | Correct | 9 ms | 9984 KB | Output is correct |
21 | Correct | 9 ms | 9984 KB | Output is correct |
22 | Correct | 8 ms | 10112 KB | Output is correct |
23 | Correct | 11 ms | 9892 KB | Output is correct |
24 | Correct | 9 ms | 9984 KB | Output is correct |
25 | Correct | 9 ms | 9984 KB | Output is correct |
26 | Correct | 10 ms | 9984 KB | Output is correct |
27 | Correct | 9 ms | 9984 KB | Output is correct |
28 | Correct | 9 ms | 9984 KB | Output is correct |
29 | Correct | 9 ms | 9984 KB | Output is correct |
30 | Correct | 9 ms | 9984 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 645 ms | 41976 KB | Output is correct |
2 | Correct | 213 ms | 42360 KB | Output is correct |
3 | Correct | 629 ms | 41592 KB | Output is correct |
4 | Correct | 217 ms | 42488 KB | Output is correct |
5 | Correct | 618 ms | 38648 KB | Output is correct |
6 | Correct | 220 ms | 42376 KB | Output is correct |
7 | Correct | 596 ms | 38944 KB | Output is correct |
8 | Correct | 211 ms | 42104 KB | Output is correct |
9 | Correct | 671 ms | 37396 KB | Output is correct |
10 | Correct | 656 ms | 34852 KB | Output is correct |
11 | Correct | 701 ms | 37884 KB | Output is correct |
12 | Correct | 646 ms | 40312 KB | Output is correct |
13 | Correct | 638 ms | 34424 KB | Output is correct |
14 | Correct | 675 ms | 40712 KB | Output is correct |
15 | Correct | 649 ms | 40568 KB | Output is correct |
16 | Correct | 651 ms | 35476 KB | Output is correct |
17 | Correct | 647 ms | 35960 KB | Output is correct |
18 | Correct | 652 ms | 36244 KB | Output is correct |
19 | Correct | 666 ms | 39208 KB | Output is correct |
20 | Correct | 656 ms | 41592 KB | Output is correct |
21 | Correct | 8 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 9728 KB | Output is correct |
2 | Correct | 7 ms | 9728 KB | Output is correct |
3 | Correct | 7 ms | 9728 KB | Output is correct |
4 | Correct | 7 ms | 9728 KB | Output is correct |
5 | Correct | 7 ms | 9728 KB | Output is correct |
6 | Correct | 7 ms | 9728 KB | Output is correct |
7 | Correct | 7 ms | 9728 KB | Output is correct |
8 | Correct | 7 ms | 9728 KB | Output is correct |
9 | Correct | 7 ms | 9728 KB | Output is correct |
10 | Correct | 8 ms | 9728 KB | Output is correct |
11 | Correct | 9 ms | 9888 KB | Output is correct |
12 | Correct | 9 ms | 9856 KB | Output is correct |
13 | Correct | 9 ms | 9856 KB | Output is correct |
14 | Correct | 9 ms | 9856 KB | Output is correct |
15 | Correct | 9 ms | 9984 KB | Output is correct |
16 | Correct | 9 ms | 9984 KB | Output is correct |
17 | Correct | 10 ms | 9984 KB | Output is correct |
18 | Correct | 10 ms | 10112 KB | Output is correct |
19 | Correct | 9 ms | 9984 KB | Output is correct |
20 | Correct | 9 ms | 9984 KB | Output is correct |
21 | Correct | 9 ms | 9984 KB | Output is correct |
22 | Correct | 8 ms | 10112 KB | Output is correct |
23 | Correct | 11 ms | 9892 KB | Output is correct |
24 | Correct | 9 ms | 9984 KB | Output is correct |
25 | Correct | 9 ms | 9984 KB | Output is correct |
26 | Correct | 10 ms | 9984 KB | Output is correct |
27 | Correct | 9 ms | 9984 KB | Output is correct |
28 | Correct | 9 ms | 9984 KB | Output is correct |
29 | Correct | 9 ms | 9984 KB | Output is correct |
30 | Correct | 9 ms | 9984 KB | Output is correct |
31 | Correct | 645 ms | 41976 KB | Output is correct |
32 | Correct | 213 ms | 42360 KB | Output is correct |
33 | Correct | 629 ms | 41592 KB | Output is correct |
34 | Correct | 217 ms | 42488 KB | Output is correct |
35 | Correct | 618 ms | 38648 KB | Output is correct |
36 | Correct | 220 ms | 42376 KB | Output is correct |
37 | Correct | 596 ms | 38944 KB | Output is correct |
38 | Correct | 211 ms | 42104 KB | Output is correct |
39 | Correct | 671 ms | 37396 KB | Output is correct |
40 | Correct | 656 ms | 34852 KB | Output is correct |
41 | Correct | 701 ms | 37884 KB | Output is correct |
42 | Correct | 646 ms | 40312 KB | Output is correct |
43 | Correct | 638 ms | 34424 KB | Output is correct |
44 | Correct | 675 ms | 40712 KB | Output is correct |
45 | Correct | 649 ms | 40568 KB | Output is correct |
46 | Correct | 651 ms | 35476 KB | Output is correct |
47 | Correct | 647 ms | 35960 KB | Output is correct |
48 | Correct | 652 ms | 36244 KB | Output is correct |
49 | Correct | 666 ms | 39208 KB | Output is correct |
50 | Correct | 656 ms | 41592 KB | Output is correct |
51 | Correct | 8 ms | 9728 KB | Output is correct |
52 | Correct | 510 ms | 25012 KB | Output is correct |
53 | Correct | 512 ms | 24956 KB | Output is correct |
54 | Correct | 502 ms | 25080 KB | Output is correct |
55 | Correct | 521 ms | 24952 KB | Output is correct |
56 | Correct | 497 ms | 24952 KB | Output is correct |
57 | Correct | 499 ms | 24952 KB | Output is correct |
58 | Correct | 501 ms | 28920 KB | Output is correct |
59 | Correct | 474 ms | 29048 KB | Output is correct |
60 | Correct | 582 ms | 28444 KB | Output is correct |
61 | Correct | 608 ms | 28152 KB | Output is correct |
62 | Correct | 220 ms | 42324 KB | Output is correct |
63 | Correct | 213 ms | 42360 KB | Output is correct |
64 | Correct | 214 ms | 42104 KB | Output is correct |
65 | Correct | 215 ms | 42360 KB | Output is correct |
66 | Execution timed out | 3071 ms | 33600 KB | Time limit exceeded |
67 | Halted | 0 ms | 0 KB | - |