Submission #1018765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018765		cot7302	Railway (BOI17_railway)	C++17	100 / 100	58 ms	41672 KiB

railway

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q, k; cin >> n >> q >> k;
    vec<vec<pair<int, int>>> G(n);
    vec<int> parent(n), pa_edge(n), head(n), depth(n), dfn(n), order(n), sum(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        --x, --y;
        G[x].emplace_back(y, i);
        G[y].emplace_back(x, i);
    }
    {
        vec<int> heavy(n, -1);
        auto get_heavy = [&](auto&& f, int x, int pre) -> int {
            int ret{1}, heavy_sz{0};
            for (auto [to, i] : G[x]) if (to != pre) {
                parent[to] = x;
                pa_edge[to] = i;
                depth[to] = depth[x] + 1;
                auto to_sz = f(f, to, x);
                ret += to_sz;
                if (to_sz > heavy_sz) heavy[x] = to, heavy_sz = to_sz;
            }
            return ret;
        };
        get_heavy(get_heavy, 0, -1);
        int t = 0;
        auto dfs = [&](auto&& f, int x, int pre, int hd) -> void {
            head[x] = hd;
            dfn[x] = t++;
            order[dfn[x]] = x;
            if (heavy[x] != -1) f(f, heavy[x], x, hd);
            for (auto [to, i] : G[x]) if (to != pre && to != heavy[x])
                f(f, to, x, to);
        };
        dfs(dfs, 0, -1, 0);
    }

    auto lca = [&](int x, int y) -> int {
        while (head[x] != head[y]) {
            if (depth[head[x]] < depth[head[y]]) swap(x, y);
            x = parent[head[x]];
        }
        return depth[x] < depth[y] ? x : y;
    };

    auto get_virtual_tree_edges = [&](vec<int> a) -> vec<pair<int, int>> {
        sort(ALL(a), [&](const auto lhs, const auto rhs) { return dfn[lhs] < dfn[rhs]; });
        for (int i = 1, sz = (int)size(a); i < sz; i++) {
            a.emplace_back(lca(a[i - 1], a[i]));
        }
        sort(ALL(a), [&](const auto lhs, const auto rhs) { return dfn[lhs] < dfn[rhs]; });
        a.resize(unique(ALL(a)) - begin(a));
        vec<pair<int, int>> ret(size(a) - 1);
        for (int i = 1; i < (int)size(a); i++) ret[i - 1] = {lca(a[i - 1], a[i]), a[i]};
        return ret;
    };

    while (q--) {
        int s; cin >> s;
        vec<int> a(s);
        for (auto& x : a) {
            cin >> x;
            --x;
        }
        for (auto [pa, x] : get_virtual_tree_edges(a)) {
            while (head[pa] != head[x]) {
                ++sum[dfn[head[x]]];
                --sum[dfn[x] + 1];
                x = parent[head[x]];
            }
            ++sum[dfn[pa] + 1];
            --sum[dfn[x] + 1];
        }
    }

    inclusive_scan(ALL(sum), begin(sum));

    vec<int> ans;
    for (int i = 1; i < n; i++) if (sum[i] >= k) ans.emplace_back(pa_edge[order[i]]);
    sort(ALL(ans));
    cout << size(ans) << '\n';
    for (auto x : ans) cout << x << ' ';
    if (!empty(ans)) cout << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25