Submission #931621

#	Time	Username	Problem	Language	Result	Execution time	Memory
931621		vjudge1	Capital City (JOI20_capital_city)	C++17	11 / 100	3041 ms	27472 KiB

capital_city

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

const int N = 2e5 + 10, INF = 1e9;

bool mark[N], flag[N];
int n, k, C[N], ans = INF, ptr, p[N];
vector<int> G[N], vec[N];
queue<int> q;

void dfs1(int v) {
    ptr++;
    for (auto e : vec[v])
        if (!mark[e]) q.push(e);
    flag[v] = true;
}

void dfs2(int v, int par) {
    p[v] = par;
    for (auto e : G[v])
        if (e ^ par) dfs2(e, v);
}

void f(int v) {
    if (!mark[v]) {
        if (!flag[C[v]]) dfs1(C[v]);
        f(p[v]);
    }
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        C[i] = c;
        vec[c].pb(i);
    }
    ans = k;
    for (int i = 1; i <= k; i++) {
        if (vec[i].size()) {
            mark[*vec[i].begin()] = true;
            ptr = 0, dfs1(i);
            dfs2(*vec[i].begin(), 0);
            while (!q.empty()) {
                auto u = q.front();
                q.pop(), f(u);
            }
            ans = min(ans, ptr);
            for (int j = 1; j <= n; j++) flag[j] = false;
            for (int j = 1; j <= n; j++) mark[j] = false;
        }
    }
    cout << ans - 1 << endl;
}

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