oj.uz

Submission #448247

# Submission time Handle Problem Language Result Execution time Memory
448247 2021-07-29T12:29:17 Z JovanB Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 38540 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;
            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()) cnt = N;
      |                ~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9668 KB Output is correct
4 Correct 6 ms 9648 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9732 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 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 9728 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9668 KB Output is correct
4 Correct 6 ms 9648 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9732 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 8 ms 9804 KB Output is correct
12 Correct 8 ms 9804 KB Output is correct
13 Correct 8 ms 9876 KB Output is correct
14 Correct 8 ms 9804 KB Output is correct
15 Correct 8 ms 9836 KB Output is correct
16 Correct 8 ms 9804 KB Output is correct
17 Correct 10 ms 9872 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 8 ms 9856 KB Output is correct
20 Correct 9 ms 9932 KB Output is correct
21 Correct 8 ms 9932 KB Output is correct
22 Correct 8 ms 10008 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9872 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 9 ms 10044 KB Output is correct
27 Correct 9 ms 10008 KB Output is correct
28 Correct 9 ms 9932 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 8 ms 9932 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 38120 KB Output is correct
2 Correct 281 ms 38540 KB Output is correct
3 Correct 1008 ms 37712 KB Output is correct
4 Correct 274 ms 38388 KB Output is correct
5 Correct 1397 ms 34716 KB Output is correct
6 Correct 285 ms 38416 KB Output is correct
7 Correct 1980 ms 35092 KB Output is correct
8 Correct 1773 ms 38140 KB Output is correct
9 Execution timed out 3069 ms 32980 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9728 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9668 KB Output is correct
4 Correct 6 ms 9648 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9732 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Correct 8 ms 9804 KB Output is correct
12 Correct 8 ms 9804 KB Output is correct
13 Correct 8 ms 9876 KB Output is correct
14 Correct 8 ms 9804 KB Output is correct
15 Correct 8 ms 9836 KB Output is correct
16 Correct 8 ms 9804 KB Output is correct
17 Correct 10 ms 9872 KB Output is correct
18 Correct 9 ms 9876 KB Output is correct
19 Correct 8 ms 9856 KB Output is correct
20 Correct 9 ms 9932 KB Output is correct
21 Correct 8 ms 9932 KB Output is correct
22 Correct 8 ms 10008 KB Output is correct
23 Correct 8 ms 9932 KB Output is correct
24 Correct 8 ms 9872 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 9 ms 10044 KB Output is correct
27 Correct 9 ms 10008 KB Output is correct
28 Correct 9 ms 9932 KB Output is correct
29 Correct 8 ms 9932 KB Output is correct
30 Correct 8 ms 9932 KB Output is correct
31 Correct 1073 ms 38120 KB Output is correct
32 Correct 281 ms 38540 KB Output is correct
33 Correct 1008 ms 37712 KB Output is correct
34 Correct 274 ms 38388 KB Output is correct
35 Correct 1397 ms 34716 KB Output is correct
36 Correct 285 ms 38416 KB Output is correct
37 Correct 1980 ms 35092 KB Output is correct
38 Correct 1773 ms 38140 KB Output is correct
39 Execution timed out 3069 ms 32980 KB Time limit exceeded
40 Halted 0 ms 0 KB -