oj.uz

Submission #428446

# Submission time Handle Problem Language Result Execution time Memory
428446 2021-06-15T11:53:54 Z tengiz05 Capital City (JOI20_capital_city) C++17
0 / 100
 3000 ms 104508 KB 
#include <bits/stdc++.h>
constexpr int N = 2e5;
std::vector<int> e[N], edges[N], rev[N];
int c[N], up[N][20], in[N], out[N], timeStamp, lc[N], 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;
std::vector<int> ne[N];
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];
std::vector<int> comp[N];
void dfs3(int u) {
    comp[timer].push_back(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]) {
            // std::cout << c[i] + 1 << " " << c[u] + 1 << "\n";
            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);
        // for (auto x : comp[timer]) {
        //     std::cout << x + 1 << " ";
        // }std::cout << "\n\n";
        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]);
                // std::cout << belong[i] << " " << belong[v] << "\n";
            }
        }
    }
    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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25396 KB Output is correct
2 Correct 15 ms 25292 KB Output is correct
3 Correct 15 ms 25380 KB Output is correct
4 Incorrect 16 ms 25416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25396 KB Output is correct
2 Correct 15 ms 25292 KB Output is correct
3 Correct 15 ms 25380 KB Output is correct
4 Incorrect 16 ms 25416 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 104508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25396 KB Output is correct
2 Correct 15 ms 25292 KB Output is correct
3 Correct 15 ms 25380 KB Output is correct
4 Incorrect 16 ms 25416 KB Output isn't correct
5 Halted 0 ms 0 KB -