Submission #1042892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042892		Sharky	Capital City (JOI20_capital_city)	C++17	100 / 100	362 ms	47132 KiB

capital_city

// https://oj.uz/submission/954992

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

const int N = 200008;

int n, k, cnt = 0, bl[N] /* block */, a[N], c[N], vis[N], g[N], ans = (int) 1e18, par[N], sz[N];
vector<int> adj[N], vt[N];

void dfs_sz(int u, int p) {
    bl[u] = cnt;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p || c[v]) continue;
        dfs_sz(v, u);
        sz[u] += sz[v];
    }
}

int find(int u, int p, int tot) {
    int mx = -1, ret = -1;
    for (int v : adj[u]) {
        if (v == p || c[v]) continue;
        ret = max(ret, find(v, u, tot));
        mx = max(mx, sz[v]);
    }
    mx = max(mx, tot - sz[u]);
    if (mx <= tot / 2) return u;
    return ret;
}

void dfs_par(int u, int p) {
    for (int v : adj[u]) {
        if (v == p || c[v]) continue;
        dfs_par(v, u);
        par[v] = u;
    }
}

void solve(int u) {
    int cur = 0;
    ++cnt;
    dfs_sz(u, -1);
    int cent = find(u, -1, sz[u]);
    c[cent] = 1;
    dfs_par(cent, -1);
    queue<int> q;
    bool ok = 1;
    g[a[cent]] = cnt;
    q.push(a[cent]);
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        cur++;
        for (int v : vt[node]) {
            if (bl[v] != cnt) {
                ok = 0;
                break;
            }
            int x = v;
            while (vis[x] != cnt) {
                if (g[a[x]] != cnt) {
                    g[a[x]] = cnt;
                    q.push(a[x]);
                }
                vis[x] = cnt;
                if (x == cent) break;
                x = par[x];
            }
        }
        if (!ok) break;
    }
    if (ok) ans = min(ans, cur);
    for (int v : adj[cent]) if (!c[v]) solve(v);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        g[i] = vis[i] = -1;
        cin >> a[i];
        vt[a[i]].push_back(i);
    }
    solve(1);
    cout << ans - 1 << '\n';
}

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