Submission #427920

#	Time	Username	Problem	Language	Result	Execution time	Memory
427920		tengiz05	Capital City (JOI20_capital_city)	C++17	0 / 100	3080 ms	42904 KiB

capital_city

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k;
    std::cin >> n >> k;
    if (n == 1) {
        std::cout << 0 << "\n";
        return 0;
    }
    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    std::vector<int> c(n);
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
        c[i]--;
    }
    std::vector<int> in(n), out(n), L(k, n), R(k);
    int timeStamp = 0;
    std::function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = timeStamp++;
        for (auto v : e[u]) {
            if (v != p) {
                dfs(v, u);
            }
        }
        out[u] = timeStamp;
    };
    int rt = -1;
    for (int i = 0; i < n; i++) {
        if (e[i].size() == 1) {
            rt = i;
        }
    }
    dfs(rt, rt);
    std::vector<bool> vis(k);
    std::set<std::pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        s.emplace(in[i], c[i]);
        L[c[i]] = std::min(L[c[i]], in[i]);
        R[c[i]] = std::max(R[c[i]], in[i]);
    }
    std::vector<int> ans(k);
    int res = 1e9;
    for (int it = 0; it <= k; it++) {
        vis.assign(k, false);
        for (int i = 0; i < k; i++) {
            if (!vis[i]) {
                int l = L[i], r = R[i];
                bool ok = false;
                while (true) {
                    auto it = s.lower_bound({l, -1});
                    if (it == s.end() || it->first > r) {
                        ok = true;
                        break;
                    }
                    if (vis[it->second]) {
                        s.erase(it);
                        continue;
                    }
                    int color = it->second;
                    vis[color] = true;
                    l = std::min(l, L[color]);
                    r = std::max(r, R[color]);
                    s.erase(it);
                    ans[i] += ans[color] + 1;
                    break;
                }
                if (ok) {
                    res = std::min(res, ans[i]);
                }
            }
        }
    }
    std::cout << res << "\n";
    return 0;
}

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