oj.uz

Submission #805371

# Submission time Handle Problem Language Result Execution time Memory
805371 2023-08-03T15:53:39 Z FedShat Capital City (JOI20_capital_city) C++17
1 / 100
 1796 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct LCA {
    static constexpr int k = 18;
    vector<vector<int>> up;
    vector<int> depth;

    LCA() {}
    LCA(int n) {
        up.resize(k, vector<int>(n));
        depth.resize(n);
    }

    void add_leaf(int v, int p) {
        depth[v] = depth[p] + 1;
        up[0][v] = p;
        for (int i = 1; i < k; ++i) {
            up[i][v] = up[i - 1][up[i - 1][v]];
        }
    }

    int up_d(int v, int d) {
        for (int i = k - 1; i >= 0; --i) {
            if (d >= (1 << i)) {
                v = up[i][v];
                d -= (1 << i);
            }
        }
        return v;
    }

    int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            swap(u, v);
        }
        u = up_d(u, depth[u] - depth[v]);
        for (int i = k - 1; i >= 0; --i) {
            if (up[i][u] != up[i][v]) {
                u = up[i][u];
                v = up[i][v];
            }
        }
        if (u == v) {
            return u;
        }
        return up[0][u];
    }
};

vector<vector<int>> tr, g, gg;
vector<int> tin, tout, c, ggg;
int timer = 0;
LCA st;

void add(int v, int p) {
    g.emplace_back();
    ggg[v] = g.size() - 1;
    g.back().push_back(c[v]);
    gg[0][v] = ggg[p];
    for (int i = 1; i < LCA::k; ++i) {
        g.emplace_back();
        gg[i][v] = g.size() - 1;
        g.back().emplace_back(gg[i - 1][v]);
        g.back().emplace_back(gg[i - 1][st.up[i - 1][v]]);
    }
}

void dfs(int v, int p) {
    tin[v] = timer++;
    for (auto u : tr[v]) {
        if (u != p) {
            st.add_leaf(u, v);
            add(u, v);
            dfs(u, v);
        }
    }
    tout[v] = timer;
}

vector<bool> used;
vector<int> topsort;

void dfs1(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs1(u);
        }
    }
    topsort.push_back(v);
}

vector<vector<int>> gr;
vector<int> cond, siz;
int cnt = 0;
int k;

void dfs2(int v) {
    used[v] = 1;
    cond[v] = cnt;
    siz[cnt] += (v < k);
    for (auto u : gr[v]) {
        if (!used[u]) {
            dfs2(u);
        }
    }
}

vector<vector<int>> gcond;
vector<int> dp;

void dfs3(int v) {
    used[v] = 1;
    dp[v] = siz[v];
    for (auto u : gcond[v]) {
        if (!used[u]) {
            dfs3(u);
        }
        dp[v] += dp[u];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n;
    cin >> n >> k;
    tr.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    c.resize(n);
    cin >> c;
    for (auto &i : c) {
        --i;
    }
    tin.resize(n);
    tout.resize(n);
    st = LCA(n);
    g.resize(k);
    gg.resize(LCA::k, vector<int>(n));
    ggg.resize(n);
    dfs(0, -1);
    vector<vector<int>> cc(k);
    for (int i = 0; i < n; ++i) {
        cc[c[i]].push_back(i);
    }
    auto add_edges = [&](int v, int d) {
        int cv = c[v];
        for (int i = 0; i < d; ++i) {
            v = st.up[0][v];
            g[cv].push_back(c[v]);
        }
        // for (int i = LCA::k - 1; i >= 0; --i) {
        //     if (d >= (1 << i)) {
        //         g[cv].push_back(gg[i][v]);
        //         d -= (1 << i);
        //         v = st.up[i][v];
        //     }
        // }
    };
    for (int i = 0; i < k; ++i) {
        sort(cc[i].begin(), cc[i].end(), [&](int u, int v) {
            return tin[u] < tin[v];
        });
        for (int j = 0; j + 1 < (int) cc[i].size(); ++j) {
            int l = st.lca(cc[i][j], cc[i][j + 1]);
            add_edges(cc[i][j], st.depth[cc[i][j]] - st.depth[l]);
            add_edges(cc[i][j + 1], st.depth[cc[i][j + 1]] - st.depth[l]);
        }
    }
    // for (int i = 0; i < k; ++i) {
    //     for (int j : g[i]) {
    //         cout << i + 1 << " " << j + 1 << "\n";
    //     }
    // }
    int sz = g.size();
    gr.resize(sz);
    for (int i = 0; i < sz; ++i) {
        for (int j : g[i]) {
            gr[j].push_back(i);
        }
    }
    used.resize(sz);
    for (int i = 0; i < sz; ++i) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    used.assign(sz, 0);
    cond.resize(sz);
    reverse(topsort.begin(), topsort.end());
    for (int i : topsort) {
        if (!used[i]) {
            siz.emplace_back();
            dfs2(i);
            ++cnt;
        }
    }
    gcond.resize(cnt);
    for (int i = 0; i < sz; ++i) {
        for (int j : g[i]) {
            if (cond[i] != cond[j]) {
                gcond[cond[i]].push_back(cond[j]);
            }
        }
    }
    for (int i = 0; i < cnt; ++i) {
        sort(gcond[i].begin(), gcond[i].end());
        gcond[i].resize(unique(gcond[i].begin(), gcond[i].end()) - gcond[i].begin());
    }
    used.assign(cnt, 0);
    dp.resize(cnt);
    for (int i = 0; i < cnt; ++i) {
        if (!used[i]) {
            dfs3(i);
        }
    }
    cout << *min_element(dp.begin(), dp.end()) - 1;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 11 ms 7472 KB Output is correct
12 Correct 12 ms 7600 KB Output is correct
13 Correct 11 ms 7600 KB Output is correct
14 Correct 11 ms 7584 KB Output is correct
15 Incorrect 13 ms 8296 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1796 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 11 ms 7472 KB Output is correct
12 Correct 12 ms 7600 KB Output is correct
13 Correct 11 ms 7600 KB Output is correct
14 Correct 11 ms 7584 KB Output is correct
15 Incorrect 13 ms 8296 KB Output isn't correct
16 Halted 0 ms 0 KB -