oj.uz

Submission #448242

# Submission time Handle Problem Language Result Execution time Memory
448242 2021-07-29T12:21:17 Z JovanB Capital City (JOI20_capital_city) C++17
1 / 100
 254 ms 40956 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];

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_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++;
            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);
        dfs_clear(v, 0);
    }
}

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];
    res = k - 1;
    decompose();
    cout << res << "\n";
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 6 ms 9724 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 6 ms 9676 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 6 ms 9724 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 6 ms 9676 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 7 ms 9804 KB Output is correct
13 Correct 8 ms 9804 KB Output is correct
14 Correct 8 ms 9860 KB Output is correct
15 Incorrect 8 ms 9804 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 40444 KB Output is correct
2 Correct 132 ms 40956 KB Output is correct
3 Correct 247 ms 40160 KB Output is correct
4 Correct 120 ms 40944 KB Output is correct
5 Incorrect 246 ms 37288 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9720 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 6 ms 9724 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 6 ms 9676 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 7 ms 9804 KB Output is correct
13 Correct 8 ms 9804 KB Output is correct
14 Correct 8 ms 9860 KB Output is correct
15 Incorrect 8 ms 9804 KB Output isn't correct
16 Halted 0 ms 0 KB -