oj.uz

Submission #537569

# Submission time Handle Problem Language Result Execution time Memory
537569 2022-03-15T08:49:03 Z Vladth11 Capital City (JOI20_capital_city) C++14
1 / 100
 203 ms 38360 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
 
const ll NMAX = 200001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 21;
 
vector <int> v[NMAX], colors[NMAX];
 
int c[NMAX];
int viz[NMAX];
int instance[NMAX];
int stamp;
int added[NMAX];
int p[NMAX];
int sz[NMAX];
int minim = 2e9;
int total = 0;
 
void getSize(int node, int p){
    sz[node] = 1;
    for(auto x : v[node]){
        if(viz[x] || x == p) continue;
        getSize(x, node);
        sz[node] += sz[x];
    }
  	total = sz[node];
}
 
int findCentroid(int node, int p){
    for(auto x : v[node]){
        if(x == p || viz[x]) continue;
        if(sz[x] > total / 2){
            return findCentroid(x, node);
        }
    }
    return node;
}
 
int getCentroid(int node){
    getSize(node, 0);
    return findCentroid(node, 0);
}
 
void DFS(int node, int parent){
    p[node] = parent;
    instance[node] = stamp;
    for(auto x : v[node]){
        if(x == parent) continue;
        if(viz[x]) continue;
        DFS(x, node);
    }
}
 
void Centroid(int node){
    int centroid = getCentroid(node);
    viz[centroid] = 1;
    stamp++;
    instance[centroid] = stamp;
    for(auto x : v[centroid]){
        if(viz[x])
            continue;
        DFS(x, centroid);
    }
    queue <int> q;
    int ok = 1;
    q.push(c[centroid]);
    added[c[centroid]] = stamp;
    int cnt = 1;
    while(q.size()){
        int color = q.front();
        q.pop();
        for(auto x : colors[color]){
            if(instance[x] != stamp){
                ok = 0;
                break;
            }
            if(x != centroid && added[c[p[x]]] != stamp){
                q.push(c[p[x]]);
                added[c[p[x]]] = stamp;
                cnt++;
            }
        }
        if(!ok)
            break;
    }
    if(ok){
        minim = min(minim, cnt - 1);
    }
    for(auto x : v[node]){
        if(viz[x]) continue;
        Centroid(x);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, i, k;
    cin >> n >> k;
    for(i = 2; i <= n; i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i = 1; i <= n; i++){
        cin >> c[i];
        colors[c[i]].push_back(i);
    }
    Centroid(1);
    cout << minim;
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9704 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9884 KB Output is correct
14 Correct 8 ms 9812 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Incorrect 6 ms 9860 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 37620 KB Output is correct
2 Correct 104 ms 38360 KB Output is correct
3 Correct 175 ms 37684 KB Output is correct
4 Correct 99 ms 38264 KB Output is correct
5 Incorrect 194 ms 34984 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9704 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 7 ms 9812 KB Output is correct
13 Correct 7 ms 9884 KB Output is correct
14 Correct 8 ms 9812 KB Output is correct
15 Correct 6 ms 9940 KB Output is correct
16 Incorrect 6 ms 9860 KB Output isn't correct
17 Halted 0 ms 0 KB -