oj.uz

Submission #428496

# Submission time Handle Problem Language Result Execution time Memory
428496 2021-06-15T12:19:42 Z tengiz05 Capital City (JOI20_capital_city) C++17
1 / 100
 3000 ms 98848 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20684 KB Output is correct
2 Correct 14 ms 20712 KB Output is correct
3 Correct 14 ms 20684 KB Output is correct
4 Correct 16 ms 20704 KB Output is correct
5 Correct 14 ms 20676 KB Output is correct
6 Correct 17 ms 20628 KB Output is correct
7 Correct 14 ms 20716 KB Output is correct
8 Correct 16 ms 20684 KB Output is correct
9 Correct 15 ms 20672 KB Output is correct
10 Correct 15 ms 20688 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20684 KB Output is correct
2 Correct 14 ms 20712 KB Output is correct
3 Correct 14 ms 20684 KB Output is correct
4 Correct 16 ms 20704 KB Output is correct
5 Correct 14 ms 20676 KB Output is correct
6 Correct 17 ms 20628 KB Output is correct
7 Correct 14 ms 20716 KB Output is correct
8 Correct 16 ms 20684 KB Output is correct
9 Correct 15 ms 20672 KB Output is correct
10 Correct 15 ms 20688 KB Output is correct
11 Correct 17 ms 21196 KB Output is correct
12 Correct 16 ms 21196 KB Output is correct
13 Correct 15 ms 21276 KB Output is correct
14 Correct 16 ms 21228 KB Output is correct
15 Execution timed out 3094 ms 21300 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 98848 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 20684 KB Output is correct
2 Correct 14 ms 20712 KB Output is correct
3 Correct 14 ms 20684 KB Output is correct
4 Correct 16 ms 20704 KB Output is correct
5 Correct 14 ms 20676 KB Output is correct
6 Correct 17 ms 20628 KB Output is correct
7 Correct 14 ms 20716 KB Output is correct
8 Correct 16 ms 20684 KB Output is correct
9 Correct 15 ms 20672 KB Output is correct
10 Correct 15 ms 20688 KB Output is correct
11 Correct 17 ms 21196 KB Output is correct
12 Correct 16 ms 21196 KB Output is correct
13 Correct 15 ms 21276 KB Output is correct
14 Correct 16 ms 21228 KB Output is correct
15 Execution timed out 3094 ms 21300 KB Time limit exceeded
16 Halted 0 ms 0 KB -