제출 #947513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947513		weakweakweak	수도 (JOI20_capital_city)	C++17	100 / 100	499 ms	57052 KiB

capital_city

//又抄解
#include <bits/stdc++.h>
using namespace std;

const int N = 510000;
int n, k, col[N], sz[N], parr[N], vis[N] = {0}, ans = INT_MAX, ins[N] = {0}, tt = 3, tt2 = 5;
bool block[N] = {0}, finish[N] = {0};
vector <int> e[N], bel[N];


int dfs_sz (int i, int par) {
    sz[i] = 1;
    parr[i] = par;
    for (int j : e[i]) if (j != par and !block[j]) {
        dfs_sz (j, i);
        sz[i] += sz[j];
    }
    vis[i] = tt;
return sz[i];}

int dfs_cen (int i, int par, int tot) {
    for (int j : e[i]) if (j != par and !block[j] and sz[j] * 2 > tot) return dfs_cen(j, i, tot);
    return i;
}

void solve (int st) {
    vector <int> color_used = {st};
    queue<int> q;
    tt2++;
    ins[st] = tt2;
    for (int j : bel[st]) {
        q.push(j);
        if (vis[j] != tt) return;
    }
    while (q.size()) {
        int i = q.front(); q.pop();
        if (ins[col[parr[i]]] != tt2) {
            ins[col[parr[i]]] = tt2;
            color_used.push_back(col[parr[i]]);
            for (int x : bel[col[parr[i]]]) {
                q.push(x);
                if (vis[x] != tt) return;
            }
        }
     }
    ans = min(ans, (int)color_used.size() - 1);
}

void CD (int i) {
    int tot = dfs_sz(i, i);
    int cen = dfs_cen(i, i, tot);
    dfs_sz(cen, cen);
    solve(col[cen]);
    block[cen] = 1;
    tt++;
    for (int j : e[cen]) if (!block[j]) CD(j);
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }   
    for (int i = 1; i <= n; i++) {
        cin >> col[i];
        bel[col[i]] . push_back(i);
    }

    CD(1);

    cout << ans << '\n';
return 0;}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59