oj.uz

Submission #448248

# Submission time Handle Problem Language Result Execution time Memory
448248 2021-07-29T12:30:10 Z JovanB Capital City (JOI20_capital_city) C++17
100 / 100
 1034 ms 38568 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;
    for(auto c : graf[v]){
        if(erased[c] || c == p) continue;
        dfs_size(c, v);
        sz[v] += sz[c];
    }
}

void dfs_set(int v, int p){
    par[v] = p;
    szc[col[v]]++;
    for(auto c : graf[v]) if(!erased[c] && c != p) dfs_set(c, v);
}

void dfs_clear(int v, int p){
    visited[v] = 0;
    viscol[col[v]] = 0;
    szc[col[v]] = 0;
    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_set(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;
                break;
            }
            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];
        vec[col[i]].push_back(i);
    }
    res = k - 1;
    decompose();
    cout << res << "\n";
    return 0;
}

Compilation message

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

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9748 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 7 ms 9804 KB Output is correct
12 Correct 7 ms 9804 KB Output is correct
13 Correct 8 ms 9824 KB Output is correct
14 Correct 9 ms 9804 KB Output is correct
15 Correct 8 ms 9804 KB Output is correct
16 Correct 8 ms 9804 KB Output is correct
17 Correct 7 ms 9932 KB Output is correct
18 Correct 7 ms 9932 KB Output is correct
19 Correct 7 ms 9932 KB Output is correct
20 Correct 7 ms 9932 KB Output is correct
21 Correct 7 ms 9932 KB Output is correct
22 Correct 7 ms 9932 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9896 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 8 ms 9932 KB Output is correct
27 Correct 8 ms 9932 KB Output is correct
28 Correct 8 ms 9960 KB Output is correct
29 Correct 8 ms 9940 KB Output is correct
30 Correct 8 ms 9932 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 37768 KB Output is correct
2 Correct 263 ms 38336 KB Output is correct
3 Correct 796 ms 37488 KB Output is correct
4 Correct 245 ms 38216 KB Output is correct
5 Correct 749 ms 34416 KB Output is correct
6 Correct 251 ms 38212 KB Output is correct
7 Correct 769 ms 34748 KB Output is correct
8 Correct 252 ms 37708 KB Output is correct
9 Correct 983 ms 32840 KB Output is correct
10 Correct 1034 ms 30576 KB Output is correct
11 Correct 927 ms 33480 KB Output is correct
12 Correct 957 ms 36092 KB Output is correct
13 Correct 1000 ms 30276 KB Output is correct
14 Correct 982 ms 36700 KB Output is correct
15 Correct 973 ms 36252 KB Output is correct
16 Correct 983 ms 31056 KB Output is correct
17 Correct 917 ms 31632 KB Output is correct
18 Correct 957 ms 31824 KB Output is correct
19 Correct 909 ms 35008 KB Output is correct
20 Correct 909 ms 37284 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 5 ms 9748 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 5 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 7 ms 9804 KB Output is correct
12 Correct 7 ms 9804 KB Output is correct
13 Correct 8 ms 9824 KB Output is correct
14 Correct 9 ms 9804 KB Output is correct
15 Correct 8 ms 9804 KB Output is correct
16 Correct 8 ms 9804 KB Output is correct
17 Correct 7 ms 9932 KB Output is correct
18 Correct 7 ms 9932 KB Output is correct
19 Correct 7 ms 9932 KB Output is correct
20 Correct 7 ms 9932 KB Output is correct
21 Correct 7 ms 9932 KB Output is correct
22 Correct 7 ms 9932 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9896 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 8 ms 9932 KB Output is correct
27 Correct 8 ms 9932 KB Output is correct
28 Correct 8 ms 9960 KB Output is correct
29 Correct 8 ms 9940 KB Output is correct
30 Correct 8 ms 9932 KB Output is correct
31 Correct 716 ms 37768 KB Output is correct
32 Correct 263 ms 38336 KB Output is correct
33 Correct 796 ms 37488 KB Output is correct
34 Correct 245 ms 38216 KB Output is correct
35 Correct 749 ms 34416 KB Output is correct
36 Correct 251 ms 38212 KB Output is correct
37 Correct 769 ms 34748 KB Output is correct
38 Correct 252 ms 37708 KB Output is correct
39 Correct 983 ms 32840 KB Output is correct
40 Correct 1034 ms 30576 KB Output is correct
41 Correct 927 ms 33480 KB Output is correct
42 Correct 957 ms 36092 KB Output is correct
43 Correct 1000 ms 30276 KB Output is correct
44 Correct 982 ms 36700 KB Output is correct
45 Correct 973 ms 36252 KB Output is correct
46 Correct 983 ms 31056 KB Output is correct
47 Correct 917 ms 31632 KB Output is correct
48 Correct 957 ms 31824 KB Output is correct
49 Correct 909 ms 35008 KB Output is correct
50 Correct 909 ms 37284 KB Output is correct
51 Correct 7 ms 9676 KB Output is correct
52 Correct 650 ms 21132 KB Output is correct
53 Correct 682 ms 21060 KB Output is correct
54 Correct 677 ms 21112 KB Output is correct
55 Correct 727 ms 21164 KB Output is correct
56 Correct 740 ms 21060 KB Output is correct
57 Correct 691 ms 21140 KB Output is correct
58 Correct 736 ms 24856 KB Output is correct
59 Correct 694 ms 25144 KB Output is correct
60 Correct 810 ms 24484 KB Output is correct
61 Correct 865 ms 24384 KB Output is correct
62 Correct 245 ms 38568 KB Output is correct
63 Correct 246 ms 38460 KB Output is correct
64 Correct 255 ms 38144 KB Output is correct
65 Correct 251 ms 38440 KB Output is correct
66 Correct 452 ms 29820 KB Output is correct
67 Correct 441 ms 29756 KB Output is correct
68 Correct 445 ms 29768 KB Output is correct
69 Correct 451 ms 29628 KB Output is correct
70 Correct 462 ms 29624 KB Output is correct
71 Correct 443 ms 29756 KB Output is correct
72 Correct 486 ms 29752 KB Output is correct
73 Correct 444 ms 28856 KB Output is correct
74 Correct 508 ms 29748 KB Output is correct
75 Correct 473 ms 29756 KB Output is correct
76 Correct 810 ms 28644 KB Output is correct
77 Correct 800 ms 26692 KB Output is correct
78 Correct 905 ms 31980 KB Output is correct
79 Correct 884 ms 29636 KB Output is correct
80 Correct 942 ms 36692 KB Output is correct
81 Correct 922 ms 33372 KB Output is correct
82 Correct 911 ms 33324 KB Output is correct
83 Correct 912 ms 29944 KB Output is correct
84 Correct 940 ms 36164 KB Output is correct
85 Correct 924 ms 34400 KB Output is correct
86 Correct 934 ms 29708 KB Output is correct
87 Correct 984 ms 31244 KB Output is correct
88 Correct 853 ms 32452 KB Output is correct
89 Correct 758 ms 28576 KB Output is correct
90 Correct 764 ms 28208 KB Output is correct
91 Correct 764 ms 30612 KB Output is correct
92 Correct 772 ms 29220 KB Output is correct
93 Correct 844 ms 29004 KB Output is correct
94 Correct 930 ms 28396 KB Output is correct
95 Correct 747 ms 29928 KB Output is correct
96 Correct 764 ms 28540 KB Output is correct
97 Correct 779 ms 30532 KB Output is correct