Submission #1033258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033258		aufan	Railway (BOI17_railway)	C++17	100 / 100	119 ms	46020 KiB

railway

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m, k;
        cin >> n >> m >> k;

        vector<vector<pair<int, int>>> v(n + 1);
        for (int i = 0; i < n - 1; i++) {
                int a, b;
                cin >> a >> b;

                v[a].push_back({b, i});
                v[b].push_back({a, i});
        }

        int tim = 0;
        vector<int> dep(n + 1, -1), tin(n + 1), tout(n + 1);
        vector<vector<int>> p(n + 1, vector<int>(20));
        
        function<void(int, int)> dfs = [&](int x, int pr) {
                dep[x] = dep[pr] + 1;
                tin[x] = ++tim;
                p[x][0] = pr;
                for (int j = 1; j < 20; j++) p[x][j] = p[p[x][j - 1]][j - 1];

                for (auto [z, i] : v[x]) {
                        if (z == pr) continue;

                        dfs(z, x);
                }

                tout[x] = tim;
        };

        dfs(1, 1);

        auto upper = [&](int x, int y) {
                return tin[x] <= tin[y] && tout[y] <= tout[x];
        };

        auto lca = [&](int x, int y) {
                if (upper(x, y)) return x;
                if (upper(y, x)) return y;

                for (int j = 19; j >= 0; j--) {
                        if (!upper(p[x][j], y)) {
                                x = p[x][j];
                        }
                }

                return p[x][0];
        };

        vector<int> dp(n + 1);
        for (int i = 0; i < m; i++) {
                int s;
                cin >> s;

                vector<int> ver;
                for (int j = 0; j < s; j++) {
                        int x;
                        cin >> x;

                        ver.push_back(x);
                }
                sort(ver.begin(), ver.end(), [&](int x, int y) {
                        return tin[x] < tin[y];
                });

                for (int j = 0; j < s - 1; j++) {
                        int z = lca(ver[j], ver[j + 1]);
                        ver.push_back(z);
                }       
                sort(ver.begin(), ver.end(), [&](int x, int y) {
                        return tin[x] < tin[y];
                });
                ver.erase(unique(ver.begin(), ver.end()), ver.end());

                vector<int> st = {ver[0]};
                for (int j = 1; j < (int)ver.size(); j++) {
                        int x = ver[j];
                        while ((int)st.size() >= 2 && !upper(st.back(), x)) {
                                dp[st.back()] += 1;
                                dp[st[(int)st.size() - 2]] -= 1;
                                st.pop_back();
                        }

                        st.push_back(x);
                }

                while ((int)st.size() >= 2) {
                        dp[st.back()] += 1;
                        dp[st[(int)st.size() - 2]] -= 1;
                        st.pop_back();
                }
        }

        vector<int> ans;

        function<void(int, int)> dfs2 = [&](int x, int p) {
                for (auto [z, i] : v[x]) {
                        if (z == p) continue;

                        dfs2(z, x);

                        if (dp[z] >= k) ans.push_back(i);
                        dp[x] += dp[z];
                }
        };

        dfs2(1, 1);
        
        sort(ans.begin(), ans.end());
        cout << (int)ans.size() << '\n';
        for (auto x : ans) cout << x + 1 << " ";
        cout << '\n';
        
        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