Submission #537577

#	Time	Username	Problem	Language	Result	Execution time	Memory
537577		Vladth11	Capital City (JOI20_capital_city)	C++14	100 / 100	620 ms	39164 KiB

capital_city

/// Asta e cea mai clean + ultima sa fie de 100
#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[centroid]){
        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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59