Submission #544374

#	Time	Username	Problem	Language	Result	Execution time	Memory
544374		OttoTheDino	Railway (BOI17_railway)	C++17	100 / 100	126 ms	29252 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<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 1e5, L = 30;
int par[mx+1][L], tin[mx+1], k, tt = 0, ad[mx+1], depth[mx+1];
vii neibs[mx+1];
vi ans;

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

int lca (int a, int b) {
    if (depth[a]<depth[b]) swap(a,b);
    int dif = depth[a]-depth[b];
    a = go_up (a, dif);

    if (a==b) return a;

    rrep (i, L-1, 0) {
        if (par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }

    return par[a][0];
}

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

int dfs2 (int u) {
    int x = ad[u];
    for (auto ve : neibs[u]) {
        if (par[u][0]==ve.fi) continue;
        int res = dfs2 (ve.fi);
        if (res>=k) ans.pb(ve.se);
        x += res;
    }
    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});
    }

    dfs(1);

    par[1][0] = 1;
    rep (i,1,L-1)
        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];
        rep (j,0,s-1) {
            cin >> x[j];
            ad[x[j]]++;
        }
        sort(x, x+s, [&](const int &a,const int &b){return tin[a]<tin[b];});
        rep (j,0,s-2) ad[lca(x[j], x[j+1])]--;
        ad[lca(x[0], x[s-1])]--;
    }

    dfs2 (1);

    cout << ans.size() << "\n";
    sort(all(ans));
    for (int a : ans) cout << a << " ";
    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