Submission #872325

#	Time	Username	Problem	Language	Result	Execution time	Memory
872325		tvladm2009	Railway (BOI17_railway)	C++17	100 / 100	87 ms	28108 KiB

railway

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        adj[x].emplace_back(y, i);
        adj[y].emplace_back(x, i);
    }

    constexpr int K = 20;
    std::vector<int> level(n + 1, 0), tin(n + 1, 0), sum(n + 1, 0), ind(n + 1, 0);
    std::vector<std::vector<int>> up(K, std::vector<int> (n + 1, 0));
    int t = 0;

    std::function<void(int, int)> dfs = [&](int u, int p) {
        tin[u] = ++t;
        up[0][u] = p;
        for (int k = 1; k < K; k++) {
            up[k][u] = up[k - 1][up[k - 1][u]];
        }
        level[u] = level[p] + 1;
        for (auto [v, w] : adj[u]) {
            if (v != p) {
                dfs(v, u);
                ind[v] = w;
            }
        }
    };
    dfs(1, 0);

    auto lca = [&] (int x, int y) {
        if (level[x] < level[y]) {
            std::swap(x, y);
        }
        for (int k = K - 1; k >= 0; k--) {
            if (level[x] - (1 << k) >= level[y]) {
                x = up[k][x];
            }
        }
        if (x == y) {
            return x;
        }
        for (int k = K - 1; k >= 0; k--) {
            if (up[k][x] != up[k][y]) {
                x = up[k][x];
                y = up[k][y];
            }
        }
        return up[0][y];
    };

    auto add = [&] (int x, int y) {
        int z = lca(x, y);
        sum[x]++;
        sum[y]++;
        sum[z] -= 2;
    };

    for (int i = 1; i <= m; i++) {
        int s;
        std::cin >> s;
        std::vector<int> x(s);
        for (int j = 0; j < s; j++) {
            std::cin >> x[j];
        }
        std::sort(x.begin(), x.end(), [&] (int x, int y) {
            return tin[x] < tin[y];
        });
        for (int j = 0; j < s; j++) {
            add(x[j], x[(j + 1) % s]);
        }
    };

    std::function<void(int, int)> dfs2 = [&] (int u, int p) {
        for (auto [v, w] : adj[u]) {
            if (v != p) {
                dfs2(v, u);
                sum[u] += sum[v];
            }
        }
    };
    dfs2(1, 0);

    std::vector<int> sol;
    for (int i = 2; i <= n; i++) {
        if (2 * k <= sum[i]) {
            sol.emplace_back(ind[i]);
        }
    }
    std::sort(sol.begin(), sol.end());
    std::cout << sol.size() << "\n";
    for (auto it : sol) {
        std::cout << it << " ";
    }
    return 0;
}

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