Submission #1097612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097612		BLOBVISGOD	Railway (BOI17_railway)	C++17	100 / 100	65 ms	22228 KiB

railway

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m,k; cin >> n >> m >> k;
    int B = __lg(n+1)+2;
    vector<vector<array<int,2>>> adj(n);
    vvi par(B+1, vi(n));
    vi d(n), ord(n), cnt(n), vis(n), E(n);
    int cc = 0;
    auto dfs = [&](int at, int dep, auto&& dfs) -> void {
        ord[at] = cc++;
        vis[at] = 1;
        d[at] = dep;
        for(auto [to,id] : adj[at]) if (!vis[to]){
            par[0][to] = at;
            E[to] = id;
            dfs(to,dep+1,dfs);
        }
    };

    rep(i,0,n-1){
        int u,v; cin >> u >> v;
        u--,v--;
        adj[u].push_back({v,i+1});
        adj[v].push_back({u,i+1});
    }

    dfs(0,0,dfs);
    rep(i,0,B) rep(j,0,n) par[i+1][j] = par[i][par[i][j]];

    auto jmp = [&](int at, int k) -> int {
        for(int i = 0; k; ++i, k/=2)
            if(k&1) at = par[i][at];
        return at;
    };
    auto lca = [&](int u, int v) -> int {
        if (d[u] < d[v]) swap(u,v);
        u = jmp(u,d[u]-d[v]);
        if (u==v) return u;
        for(int i = B; i>=0; --i)
            if (par[i][u] != par[i][v])
                u = par[i][u], v = par[i][v];
        return par[0][u];
    };

    while (m--){
        int t; cin >> t;
        vi a(t);
        rep(i,0,t) cin >> a[i], a[i]--;
        sort(all(a),[&](int u, int v){
            return ord[u] < ord[v];
        });
        int last = a[t-1];
        for(auto cur : a){
            cnt[cur]++;
            cnt[last]++;
            cnt[lca(cur,last)]-=2;
            last = cur;
        }
    }

    fill(all(vis),0);
    auto prop = [&](int at, auto&& prop) -> void {
        vis[at] = 1;
        for(auto [to,id] : adj[at]) if (!vis[to]){
            prop(to,prop);
            cnt[at] += cnt[to];
        }
    };

    prop(0,prop);

    vi ans;
    rep(i,0,n) if (cnt[i] >= 2*k) ans.push_back(E[i]);
    sort(all(ans));
    cout << sz(ans) << '\n';
    for(auto c : ans) cout << c << ' ';
    cout << '\n';
}

/*

10 3 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 9
9 10
5 2 5 4 6 8
6 1 3 5 6 4 10
3 1 5 7

*/

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