제출 #1257294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257294		MisterReaper	Capital City (JOI20_capital_city)	C++20	11 / 100	3101 ms	203740 KiB

capital_city

// File AA.cpp created on 13.08.2025 at 00:09:57
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, K;
    std::cin >> N >> K;

    std::vector<std::vector<int>> adj(N);
    for (int i = 1; i < N; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        adj[A].emplace_back(B);
        adj[B].emplace_back(A);
    }

    std::vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> C[i];
        --C[i];
    }

    std::vector<std::vector<int>> bdj(K);
    for (int c = 0; c < K; ++c) {
        int p = 0;
        while (C[p] != c) {
            p++;
        }
        auto dfs = [&](auto&& self, int v, int pr) -> bool {
            bool good = false;
            for (auto u : adj[v]) {
                if (u == pr) {
                    continue;
                }
                good |= self(self, u, v);
            }
            if (C[v] == c) {
                good = true;
            }
            if (good && C[v] != c) {
                bdj[c].emplace_back(C[v]);
            }
            return good;
        };
        dfs(dfs, p, -1);
    }

    debug(bdj);

    int n = 0, tim = 0;
    std::vector<int> tin(K, -1), low(K, -1), bel(K, -1), siz, stk;
    auto dfs = [&](auto&& self, int v) -> void {
        tin[v] = low[v] = tim++;
        stk.emplace_back(v);
        for (auto u : bdj[v]) {
            if (tin[u] == -1) {
                self(self, u);
                low[v] = std::min(low[v], low[u]);
            } else if (bel[u] == -1) {
                low[v] = std::min(low[v], tin[u]);
            }
        }
        if (tin[v] == low[v]) {
            int u;
            siz.emplace_back(0);
            do {
                u = stk.back();
                stk.pop_back();
                bel[u] = n;
                siz[n]++;
            } while (u != v);
            n++;
        }
    };
    for (int i = 0; i < K; ++i) {
        if (tin[i] == -1) {
            dfs(dfs, i);
        }
    }

    debug(bel, siz);

    std::vector<int> bad(n);
    for (int v = 0; v < K; ++v) {
        for (auto u : bdj[v]) {
            if (bel[u] != bel[v]) {
                bad[bel[v]] = true;
                break;
            }
        }
    }

    int ans = K + 1;
    for (int i = 0; i < n; ++i) {
        if (!bad[i]) {
            ans = std::min(ans, siz[i]);
        }
    }

    std::cout << ans - 1 << '\n';

    return 0;
}

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