Submission #1091266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091266		MateiKing80	Railway (BOI17_railway)	C++17	100 / 100	79 ms	28148 KiB

railway

#include <bits/stdc++.h>

using namespace std;

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

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

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

    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])
            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;
        cin >> s;
        vector<int> x(s);
        for (int j = 0; j < s; j++)
            cin >> x[j];
        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]);
    };

    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);

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

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