Submission #1155934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155934		Pekiban	Capital City (JOI20_capital_city)	C++20	11 / 100	3090 ms	38316 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;
#define pb push_back

const int N = 2e5 + 5;
vector<int> g[N], h[N];
int sz[N], c[N], p[N];
bool vis[N], visC[N], Cm[N], er[N];

void dfssz(int s, int e = -1) {
    sz[s] = 1;
    for (auto u : g[s]) {
        if (u == e || vis[u]) continue;
        dfssz(u, s);
        sz[s] += sz[u];
    }
}
int centroid(int s, int n, int e = -1) {
    for (auto u : g[s]) {
        if (u == e || vis[u])   continue;
        if (sz[u] > n/2)    return centroid(u, n, s);
    }
    return s;
}
void dfsroot(int s, bool b, int e = -1) {
    Cm[s] = 1;
    for (auto u : g[s]) {
        if (u == e || vis[u])   continue;
        p[u] = s;
        dfsroot(u, b, s);
    }
}
int ans = 1e9;
void solve(int R, int n) {
    dfssz(R);
    int nd = centroid(R, n);
    dfssz(nd);
    if (!er[c[nd]]) {
        dfsroot(nd, 1);
        queue<int> Q; Q.push(c[nd]);
        vector<int> cl = {c[nd]};
        visC[c[nd]] = 1;
        bool ok = 1;
        while (!Q.empty() && ok) {
            int C = Q.front(); Q.pop();
            if (er[C]) {
                ok = 0;
                break;
            }
            for (auto u : h[C]) {
                if (u == nd)    continue;
                int v = p[u];
                if (!Cm[v]) {
                    ok = 0;
                    er[c[v]] = 1;
                    break;
                }
                while (!visC[c[v]]) {
                    visC[c[v]] = 1;
                    Q.push(c[v]);
                    cl.pb(c[v]);
                    v = p[v];
                }
            }
        }
        dfsroot(nd, 0);
        er[c[nd]] = 1;
        for (auto i : cl)   visC[i] = 0;
        if (ok) ans = min(ans, (int)cl.size() - 1);
    }
    vis[nd] = 1;
    for (auto u : g[nd]) {
        if (vis[u]) continue;
        solve(u, sz[u]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
        h[c[i]].pb(i);
    }
    solve(1, n);
    cout << ans << '\n';
}

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