Submission #544344

#	Time	Username	Problem	Language	Result	Execution time	Memory
544344		OttoTheDino	Railway (BOI17_railway)	C++17	100 / 100	330 ms	52492 KiB

railway

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 1e5, mx2 = 30;
int tin[mx+1], tout[mx+1], tt, par[mx+1][mx2+1], k, go[mx+1];

vector<int> lca[mx+1], blebs[mx+1], ans;
vii neibs[mx+1];

set<int> st[mx+1];

void dfs (int u) {
    tin[u] = ++tt;
    for (auto vi : neibs[u]) {
        if (tin[vi.fi]) continue;
        par[vi.fi][0] = u;
        dfs (vi.fi);
    }
    tout[u] = tt;
}

void dfs2 (int u) {
    int best = 0;
    for (auto vi : neibs[u]) {
        if (vi.fi==par[u][0]) continue; 
        dfs2 (vi.fi);
        if ((int)st[go[vi.fi]].size()>=k) ans.pb(vi.se);
        if (st[go[vi.fi]].size()>st[go[best]].size()) best = vi.fi;
    }

    go[u] = (best?go[best]:u);

    for (int bleb : blebs[u]) st[go[u]].insert(bleb);

    for (auto vi : neibs[u]) {
        if (vi.fi==par[u][0] || vi.fi==best) continue;
        for (int bleb : st[go[vi.fi]]) st[go[u]].insert(bleb);
    }

    for (int l : lca[u]) st[go[u]].erase(l);
}

int go_up (int x, int d) {
    rep (i,0,mx2) {
        if (d%2) x = par[x][i];
        d /= 2;
    }
    return x;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m >> k;
    rep (i,1,n-1) {
        int u, v; cin >> u >> v;
        neibs[u].pb({v,i});
        neibs[v].pb({u,i});
    }

    par[1][0] = 1;
    dfs (1);

    rep (i,1,mx2)
        rep (j,1,n)
            par[j][i] = par[par[j][i-1]][i-1];

    rep (i,1,m) {
        int s; cin >> s;
        int x[s+1], mi = 1e9, ma = 0;
        rep (j,1,s) {
            cin >> x[j];
            blebs[x[j]].pb(i);
            mi = min(mi, tin[x[j]]);
            ma = max(ma, tout[x[j]]);
        }
        int lo = 0, hi = n-1;
        while (lo<hi) {
            int mid = (lo+hi)/2;
            int y = go_up(x[1],mid);
            if (tin[y]<=mi && tout[y]>=ma) hi = mid;
            else lo = mid+1;
        }
        lca[go_up(x[1],lo)].pb(i);
    }

    dfs2 (1);

    cout << ans.size() << "\n";
    sort(all(ans));
    for (int x : ans) cout << x << " ";
    cout << "\n";

    return 0;
}

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