Submission #947509

#	Time	Username	Problem	Language	Result	Execution time	Memory
947509		weakweakweak	수도 (JOI20_capital_city)	C++17	0 / 100	3009 ms	63252 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, vis2[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];
    }
    vis2[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++;
    vis[st] = tt2;
    for (int j : bel[st]) q.push(j);
    while (q.size()) {
        int i = q.front(); q.pop();
        // if (vis2[i] != tt) return;
        // if (vis2[parr[i]] != tt) return;
        if (finish[col[parr[i]]]) return;
        if (vis[col[parr[i]]] != tt2) {
            vis[col[parr[i]]] = tt2;
            color_used.push_back(col[parr[i]]);
            for (int x : bel[col[parr[i]]]) q.push(x);
        }
     }
    for (int c : color_used) finish[c] = 1;
    // cout << '\n';
    // for (int x : color_used) cout << x << ' ';
    // cout << '\n';
    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);
    tt++;
    if (!finish[col[cen]]) solve(col[cen]);
    block[cen] = 1;
    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: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59