Submission #1129923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129923		vladilius	Railway (BOI17_railway)	C++20	100 / 100	106 ms	20924 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, k; cin>>n>>m>>k;
    vector<int> g[n + 1];
    vector<pii> ed;
    for (int i = 1; i < n; i++){
        int x, y; cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
        ed.pb({x, y});
    }
    
    vector<int> sz(n + 1), h(n + 1), p(n + 1), d(n + 1);
    function<void(int, int)> fill = [&](int v, int pr){
        p[v] = pr;
        sz[v] = 1;
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
            if (sz[i] > sz[h[v]]){
                h[v] = i;
            }
            sz[v] += sz[i];
        }
    };
    fill(1, 0);
    
    vector<int> pos(n + 1), head(n + 1);
    int timer = 0;
    function<void(int, int)> fill_hld = [&](int v, int k){
        pos[v] = ++timer;
        head[v] = k;
        if (h[v]) fill_hld(h[v], k);
        for (int i: g[v]){
            if (pos[i]) continue;
            fill_hld(i, i);
        }
    };
    fill_hld(1, 1);

    vector<pii> all;
    auto add = [&](int x, int y){
        while (true){
            if (head[x] == head[y]){
                if (d[x] > d[y]) swap(x, y);
                if (pos[x] < pos[y]){
                    all.pb({pos[x] + 1, pos[y]});
                }
                break;
            }
            else {
                if (d[head[x]] > d[head[y]]) swap(x, y);
                all.pb({pos[head[y]], pos[y]});
                y = p[head[y]];
            }
        }
    };
    
    vector<int> pr(n + 2);
    
    while (m--){
        int s; cin>>s;
        vector<int> a(s + 1);
        for (int i = 1; i <= s; i++){
            cin>>a[i];
        }
        
        all.clear();
        for (int i = 1; i < s; i++){
            add(a[i], a[i + 1]);
        }
        
        sort(all.begin(), all.end());
        int L = all[0].ff, R = all[0].ss;
        for (auto [l, r]: all){
            if (l <= R){
                R = max(R, r);
                continue;
            }
            pr[L]++; pr[R + 1]--;
            L = l; R = r;
        }
        
        pr[L]++; pr[R + 1]--;
    }
    
    vector<int> inv(n + 1);
    for (int i = 1; i <= n; i++) inv[pos[i]] = i;
    
    vector<int> ind(n + 1);
    for (int i = 0; i < ed.size(); i++){
        auto [x, y] = ed[i];
        if (d[x] > d[y]) swap(x, y);
        ind[y] = i + 1;
    }
    
    vector<int> out;
    for (int i = 1; i <= n; i++){
        pr[i] += pr[i - 1];
        if (pr[i] >= k){
            int j = inv[i];
            out.pb(ind[j]);
        }
    }
    
    sort(out.begin(), out.end());
    
    cout<<out.size()<<"\n";
    for (int i: out){
        cout<<i<<" ";
    }
    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