oj.uz

Submission #448245

# Submission time Handle Problem Language Result Execution time Memory
448245 2021-07-29T12:25:09 Z JovanB Capital City (JOI20_capital_city) C++17
100 / 100
 1545 ms 41932 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

int res;

const int N = 200000;

int par[N+5];
vector <int> graf[N+5];
int sz[N+5];
bool erased[N+5];
bool visited[N+5];
bool viscol[N+5];
int col[N+5];
vector <int> vec[N+5];
int szc[N+5];

void dfs_size(int v, int p){
    sz[v] = 1;
    par[v] = p;
    vec[col[v]].push_back(v);
    for(auto c : graf[v]){
        if(erased[c] || c == p) continue;
        dfs_size(c, v);
        sz[v] += sz[c];
    }
}

void dfs_clear(int v, int p){
    visited[v] = 0;
    viscol[col[v]] = 0;
    vec[col[v]].clear();
    for(auto c : graf[v]) if(!erased[c] && c != p) dfs_clear(c, v);
}

int find_centroid(int v, int p, int svi){
    for(auto c : graf[v]) if(!erased[c] && c != p && 2*sz[c] > svi) return find_centroid(c, v, svi);
    return v;
}

void decompose(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        dfs_size(v, 0);
        v = find_centroid(v, 0, sz[v]);
        dfs_clear(v, 0);
        dfs_size(v, 0);
        queue <int> colors;
        colors.push(col[v]);
        viscol[col[v]] = 1;
        visited[v] = 1;
        int cnt = 0;
        while(!colors.empty()){
            int cl = colors.front();
            colors.pop();
            cnt++;
            if(szc[cl] != vec[cl].size()) cnt = N;
            for(auto c : vec[cl]){
                int x = c;
                while(!visited[x]){
                    visited[x] = 1;
                    if(!viscol[col[x]]){
                        viscol[col[x]] = 1;
                        colors.push(col[x]);
                    }
                    x = par[x];
                }
            }
        }
        res = min(res, cnt - 1);
        erased[v] = 1;
        for(auto c : graf[v]) if(!erased[c]) q.push(c);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, k;
    cin >> n >> k;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        cin >> col[i];
        szc[col[i]]++;
    }
    res = k - 1;
    decompose();
    cout << res << "\n";
    return 0;
}

Compilation message

capital_city.cpp: In function 'void decompose()':
capital_city.cpp:63:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(szc[cl] != vec[cl].size()) cnt = N;
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9732 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9732 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 8 ms 9804 KB Output is correct
12 Correct 8 ms 9820 KB Output is correct
13 Correct 8 ms 9804 KB Output is correct
14 Correct 8 ms 9804 KB Output is correct
15 Correct 8 ms 9804 KB Output is correct
16 Correct 8 ms 9924 KB Output is correct
17 Correct 8 ms 9932 KB Output is correct
18 Correct 8 ms 9872 KB Output is correct
19 Correct 8 ms 9932 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 8 ms 9932 KB Output is correct
22 Correct 8 ms 9992 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9876 KB Output is correct
25 Correct 9 ms 10000 KB Output is correct
26 Correct 9 ms 9932 KB Output is correct
27 Correct 9 ms 10016 KB Output is correct
28 Correct 8 ms 9932 KB Output is correct
29 Correct 9 ms 9932 KB Output is correct
30 Correct 9 ms 9920 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1453 ms 37932 KB Output is correct
2 Correct 315 ms 38400 KB Output is correct
3 Correct 1545 ms 37484 KB Output is correct
4 Correct 314 ms 38368 KB Output is correct
5 Correct 1336 ms 34640 KB Output is correct
6 Correct 320 ms 41932 KB Output is correct
7 Correct 1250 ms 38528 KB Output is correct
8 Correct 321 ms 41660 KB Output is correct
9 Correct 1404 ms 36668 KB Output is correct
10 Correct 1379 ms 34172 KB Output is correct
11 Correct 1375 ms 37008 KB Output is correct
12 Correct 1352 ms 40008 KB Output is correct
13 Correct 1397 ms 33860 KB Output is correct
14 Correct 1429 ms 40020 KB Output is correct
15 Correct 1398 ms 39876 KB Output is correct
16 Correct 1339 ms 34704 KB Output is correct
17 Correct 1334 ms 35304 KB Output is correct
18 Correct 1348 ms 35780 KB Output is correct
19 Correct 1356 ms 38700 KB Output is correct
20 Correct 1359 ms 41032 KB Output is correct
21 Correct 6 ms 9676 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 6 ms 9732 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 8 ms 9804 KB Output is correct
12 Correct 8 ms 9820 KB Output is correct
13 Correct 8 ms 9804 KB Output is correct
14 Correct 8 ms 9804 KB Output is correct
15 Correct 8 ms 9804 KB Output is correct
16 Correct 8 ms 9924 KB Output is correct
17 Correct 8 ms 9932 KB Output is correct
18 Correct 8 ms 9872 KB Output is correct
19 Correct 8 ms 9932 KB Output is correct
20 Correct 8 ms 9932 KB Output is correct
21 Correct 8 ms 9932 KB Output is correct
22 Correct 8 ms 9992 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9876 KB Output is correct
25 Correct 9 ms 10000 KB Output is correct
26 Correct 9 ms 9932 KB Output is correct
27 Correct 9 ms 10016 KB Output is correct
28 Correct 8 ms 9932 KB Output is correct
29 Correct 9 ms 9932 KB Output is correct
30 Correct 9 ms 9920 KB Output is correct
31 Correct 1453 ms 37932 KB Output is correct
32 Correct 315 ms 38400 KB Output is correct
33 Correct 1545 ms 37484 KB Output is correct
34 Correct 314 ms 38368 KB Output is correct
35 Correct 1336 ms 34640 KB Output is correct
36 Correct 320 ms 41932 KB Output is correct
37 Correct 1250 ms 38528 KB Output is correct
38 Correct 321 ms 41660 KB Output is correct
39 Correct 1404 ms 36668 KB Output is correct
40 Correct 1379 ms 34172 KB Output is correct
41 Correct 1375 ms 37008 KB Output is correct
42 Correct 1352 ms 40008 KB Output is correct
43 Correct 1397 ms 33860 KB Output is correct
44 Correct 1429 ms 40020 KB Output is correct
45 Correct 1398 ms 39876 KB Output is correct
46 Correct 1339 ms 34704 KB Output is correct
47 Correct 1334 ms 35304 KB Output is correct
48 Correct 1348 ms 35780 KB Output is correct
49 Correct 1356 ms 38700 KB Output is correct
50 Correct 1359 ms 41032 KB Output is correct
51 Correct 6 ms 9676 KB Output is correct
52 Correct 822 ms 24396 KB Output is correct
53 Correct 926 ms 24900 KB Output is correct
54 Correct 898 ms 24792 KB Output is correct
55 Correct 914 ms 24972 KB Output is correct
56 Correct 917 ms 24692 KB Output is correct
57 Correct 924 ms 24620 KB Output is correct
58 Correct 944 ms 28896 KB Output is correct
59 Correct 922 ms 29188 KB Output is correct
60 Correct 1254 ms 28324 KB Output is correct
61 Correct 1320 ms 28164 KB Output is correct
62 Correct 315 ms 41916 KB Output is correct
63 Correct 309 ms 41904 KB Output is correct
64 Correct 323 ms 41524 KB Output is correct
65 Correct 314 ms 41836 KB Output is correct
66 Correct 578 ms 33236 KB Output is correct
67 Correct 585 ms 33208 KB Output is correct
68 Correct 579 ms 33344 KB Output is correct
69 Correct 571 ms 33212 KB Output is correct
70 Correct 604 ms 33144 KB Output is correct
71 Correct 583 ms 33340 KB Output is correct
72 Correct 597 ms 33192 KB Output is correct
73 Correct 581 ms 32416 KB Output is correct
74 Correct 633 ms 33360 KB Output is correct
75 Correct 598 ms 33340 KB Output is correct
76 Correct 1104 ms 31928 KB Output is correct
77 Correct 1074 ms 30156 KB Output is correct
78 Correct 1339 ms 35744 KB Output is correct
79 Correct 1359 ms 33524 KB Output is correct
80 Correct 1316 ms 40344 KB Output is correct
81 Correct 1312 ms 36820 KB Output is correct
82 Correct 1371 ms 37056 KB Output is correct
83 Correct 1292 ms 33492 KB Output is correct
84 Correct 1381 ms 39572 KB Output is correct
85 Correct 1320 ms 38008 KB Output is correct
86 Correct 1353 ms 33504 KB Output is correct
87 Correct 1317 ms 34832 KB Output is correct
88 Correct 1169 ms 36068 KB Output is correct
89 Correct 1253 ms 32220 KB Output is correct
90 Correct 1244 ms 31892 KB Output is correct
91 Correct 1269 ms 34332 KB Output is correct
92 Correct 1238 ms 32956 KB Output is correct
93 Correct 1210 ms 32616 KB Output is correct
94 Correct 1230 ms 31920 KB Output is correct
95 Correct 1248 ms 33464 KB Output is correct
96 Correct 1247 ms 32140 KB Output is correct
97 Correct 1230 ms 34596 KB Output is correct