Submission #1291440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291440		mwen	Railway (BOI17_railway)	C++20	100 / 100	79 ms	34052 KiB

railway

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> con(n);
    for(int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        con[a].push_back({b, i});
        con[b].push_back({a, i});
    }
    vector<int> dep(n), order(n);
    vector<vector<int>> p(20, vector<int>(n));
    int id = 0;
    function<void(int, int, int)> dfs = [&](int curr, int prev, int d) {
        p[0][curr] = prev;
        dep[curr] = d;
        order[curr] = id++;
        for(auto [next, trackId] : con[curr]) {
            if(next == prev)
                continue;
            dfs(next, curr, d+1);
        }
    };
    dfs(0, 0, 0);
    
    for(int b = 1; b < sz(p); b++) {
        for(int i = 0; i < n; i++) {
            p[b][i] = p[b-1][p[b-1][i]];
        }
    }
    
    auto lca = [&](int x, int y) {
        for(int b = sz(p)-1; b >= 0; b--) {
            if(dep[x]-dep[y] >= (1<<b))
                x = p[b][x];
            if(dep[y]-dep[x] >= (1<<b))
                y = p[b][y];
        }
        if(x == y)
            return x;
        for(int b = sz(p)-1; b >= 0; b--) {
            if(p[b][x] != p[b][y]) {
                x = p[b][x];
                y = p[b][y];
            }
        }
        return p[0][x];
    };
    
    vector<int> track(n);
    
    auto addPath = [&](int a, int b) {
        track[a]++;
        track[b]++;
        track[lca(a,b)] -= 2;
    };
    
    while(m-->0) {
        int s;
        cin >> s;
        vector<int> places(s);
        for(int i = 0; i < s; i++) {
            cin >> places[i];
            places[i]--;
        }
        sort(all(places), [&](int a, int b) {
            return order[a] < order[b];
        });
        for(int i = 0; i < s; i++) {
            addPath(places[i], places[(i+1)%s]);
        }
    }
    
    set<int> ans;
    
    function<int(int, int)> go = [&](int curr, int prev) {
        for(auto [next, trackId] : con[curr]) {
            if(next == prev)
                continue;
            int traffic = go(next, curr);
            if(traffic/2 >= k)
                ans.insert(trackId);
            track[curr] += traffic;
        }
        return track[curr];
    };
    go(0, 0);
    
    cout << sz(ans) << "\n";
    for(auto a : ans)
        cout << a+1 << " ";
    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