Submission #1260631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260631		duonggsimp	Railway (BOI17_railway)	C++20	0 / 100	120 ms	48720 KiB

railway

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;

#define pb push_back
#define fi first
#define se second
#define endl '\n'

#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9+7;

ll n,q,k;
ll cnt;

ll h[100005];
ll par[100005][20];

ll st[100005];
ll en[100005];

ll f[100005];

vector <ii> res;
vector <ll> a[100005];
map <ii,ll> mp;

bool cmp(ll a,ll b){
    return st[a] < st[b];
}

void dfs(ll x,ll p){

    st[x] = ++cnt;
    for (ll i : a[x]){
        if (i == p) continue;
        h[i] = h[x] + 1;
        par[i][0] = x;
        dfs(i,x);
    }
    en[x] = cnt;

}

void setup(){
    for (long j=1; j<=18; j++){
        for (long i=1; i<=n; i++) par[i][j] = par[par[i][j-1]][j-1];
    }
    h[0] = -1;
}

ll lck(ll u,ll v){

    if (h[u] < h[v]) swap(u,v);
    for (long i=18; i>=0; i--){
        if (h[par[u][i]] >= h[v]) u = par[u][i];
    }

    if (u == v) return u;
    for (long i=18; i>=0; i--){
        if (par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];

}

void dfs2(ll x,ll p){

    for (ll i : a[x]){
        if (i == p) continue;
        dfs2(i,x);

        f[x] += f[i];

    }
    if (f[x] >= 2 * k) res.pb({x,par[x][0]});

}

signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q >> k;

    for (long i=1; i<n; i++){
        ll u,v; cin >> u >> v;

        a[u].pb(v);
        a[v].pb(u);

        mp[{u,v}] = mp[{v,u}] = i;
    }

    h[1] = 1;
    dfs(1,0);
    setup();

    while (q--){
        ll ski; cin >> ski;

        vector <ll> adj;
        for (long i=1; i<=ski; i++){
            ll x; cin >> x;
            adj.pb(x);
        }

        sort(adj.begin(),adj.end(),cmp);
        adj.pb(adj[0]);

        for (long i=1; i<adj.size(); i++){
            ll x = adj[i-1];
            ll y = adj[i];

            f[x]++;
            f[y]++;

            f[lck(x,y)] -= 2;
        }

    }

    dfs2(1,0);

    cout << res.size() << endl;
    for (ii i : res){
        ll x = i.fi;
        ll y = i.se;
        cout << mp[{i.fi,i.se}] << ' ';
    }


}

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