Submission #1313267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313267		hssaan_arif	Railway (BOI17_railway)	C++20	100 / 100	125 ms	50396 KiB

railway

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long
#define fi first
#define se second

const int N = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N] , m , k , In[N] , in = 1 , W[N] , sp[N][LG] , u , v , Dep[N] , sz , x;
map<pair<int,int> , int> mp;
vector<int> ans , lis[N];

void dfs(int v , int par){
    Dep[v] = Dep[par]+1;
    sp[v][0] = par;
    In[v] = in;
    in++;

    for (int u : lis[v]){
        if (par == u) continue;

        dfs(u , v);
    }

}

int lca(int u , int v){
    if (Dep[v] > Dep[u]){
        swap(u,v);
    }

    int dif = Dep[u] - Dep[v];

    for (int i=LG-1 ; i>=0 ; i--){
        if ((1<<i) & dif){
            u = sp[u][i];
        }
    }

    if (u == v){
        return u;
    }

    for (int i=LG-1 ; i>=0 ; i--){
        if (sp[u][i] != sp[v][i]){
            u = sp[u][i];
            v = sp[v][i];
        }
    }

    return sp[u][0];
}

void dfs1(int v , int par){
    for (int u : lis[v]){
        if (u==par) continue;

        dfs1(u , v);
        W[v] += W[u];
    }

    if (W[v] >= k){
        ans.pb(mp[{v,par}]);
    }
}

void solve(){
    cin >> n >> m >> k;

    for (int i=1 ; i<n ; i++){
        cin >> u >> v;
        mp[{u,v}] = mp[{v,u}] = i;
        lis[u].pb(v);
        lis[v].pb(u);
    }

    dfs(1 , 1);

    for (int i=1 ; i<LG ; i++){
        for (int j=1 ; j<=n ; j++){
            sp[j][i] = sp[sp[j][i-1]][i-1];
        }
    }

    while(m--){
        cin >> sz;
        vector<pair<int,int>> p;

        for (int i=1 ; i<=sz ; i++){
            cin >> x;
            W[x]++;
            p.pb({In[x],x});
        }
        sort(p.begin(),p.end());

        for (int i=0 ; i<sz ; i++){
            W[lca(p[i].se , p[(i+1)%sz].se)]--;
        }

    }

   

    dfs1(1 , 1);

    cout << ans.size() << endl;
    sort(ans.begin(),ans.end());

    for (int i : ans){
        cout << i << ' ';
    }
    cout << endl;

}

signed main(){
    // freopen("" , "r" , stdin);
    // freopen("" , "w" , stdout);
    // cout << setprecision(30);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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