Submission #428496

#	Time	Username	Problem	Language	Result	Execution time	Memory
428496		tengiz05	Capital City (JOI20_capital_city)	C++17	1 / 100	3094 ms	98848 KiB

capital_city

#include <bits/stdc++.h>
constexpr int N = 2e5;
std::vector<int> e[N], edges[N], rev[N], ne[N];
int c[N], up[N][20], in[N], out[N], timeStamp, mx[N][20], mn[N][20];
void dfs(int u, int p) {
    in[u] = timeStamp++;
    up[u][0] = p;
    mx[u][0] = mn[u][0] = c[u];
    for (int i = 1; i < 20; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        mn[u][i] = std::min(mn[u][i - 1], mn[up[u][i - 1]][i - 1]);
        mx[u][i] = std::max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
    }
    for (auto v : e[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
    out[u] = timeStamp;
}
inline bool is(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}
int lca(int u, int v) {
    if (is(u, v)) return u;
    if (is(v, u)) return v;
    for (int i = 19; i >= 0; i--) {
        if (!is(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}
std::vector<bool> vis;
std::vector<int> order;
void dfs2(int u) {
    vis[u] = true;
    for (auto v : edges[u]) {
        if (!vis[v]) {
            dfs2(v);
        }
    }
    order.push_back(u);
}
int belong[N], timer = 0, siz[N];
void dfs3(int u) {
    belong[u] = timer;
    siz[timer]++;
    vis[u] = true;
    for (auto v : rev[u]) {
        if (!vis[v]) {
            dfs3(v);
        }
    }
}
int dp[N];
int calc(int u) {
    if (~dp[u]) {
        return dp[u];
    }
    dp[u] = siz[u];
    for (auto v : ne[u]) {
        dp[u] += calc(v);
    }
    return dp[u];
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k;
    std::cin >> n >> k;
    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> comlca(k);
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
        c[i]--;
        comlca[c[i]] = i;
    }
    dfs(0, 0);
    for (int i = 0; i < n; i++) {
        comlca[c[i]] = lca(comlca[c[i]], i);
    }
    for (int i = 1; i < n; i++) {
        int u = i;
        for (int j = 18; j >= 0; j--) {
            if (mx[u][j + 1] == mn[u][j + 1] && (!is(up[u][j], comlca[c[i]]))) {
                u = up[u][j];
            }
        }
        u = up[u][0];
        if (c[u] != c[i] && (!is(u, comlca[c[i]]) || u == comlca[c[i]])) {
            edges[c[i]].push_back(c[u]);
            rev[c[u]].push_back(c[i]);
        }
    }
    vis.assign(k, 0);
    for (int i = 0; i < k; i++) {
        if (!vis[i]) {
            dfs2(i);
        }
    }
    memset(belong, -1, sizeof belong);
    vis.assign(k, 0);
    reverse(order.begin(), order.end());
    for (auto u : order) {
        if (vis[u]) {
            continue;
        }
        dfs3(u);
        timer++;
    }
    for (int i = 0; i < k; i++) {
        for (auto v : edges[i]) {
            if (belong[i] != belong[v]) {
                ne[belong[i]].push_back(belong[v]);
            }
        }
    }
    memset(dp, -1, sizeof dp);
    int ans = 1e9;
    for (int i = 0; i < timer; i++) {
        ans = std::min(ans, calc(i));
    }
    std::cout << ans - 1 << "\n";
    return 0;
}

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