Submission #332860

#	Time	Username	Problem	Language	Result	Execution time	Memory
332860		OttoTheDino	Railway (BOI17_railway)	C++17	23 / 100	1097 ms	45652 KiB

railway

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

#define rep(n)      for (int i = 0; i < n; ++i)
#define rep2(n)     for (int j = 0; j < n; ++j)
#define mp          make_pair
#define pb          push_back
#define all(a)      a.begin(), a.end()
#define fi          first
#define se          second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mxn = 2e5;

vii neibs[mxn];

int n, k, d[mxn], st[mxn][14];
vi nodes_ids[mxn], ans, del_ids[mxn];

void dfs (int u, int prev, int depth) {
    st[u][0] = prev, d[u] = depth;
    for (ii v : neibs[u]) if (v.fi!=prev) dfs(v.fi,u,depth+1);
}

void complete_st () {
    for (int i = 1; i <= 13; ++i)
        for (int j = 1; j <= n; ++j)
            st[j][i] = st[st[j][i-1]][i-1];
}

int find_lca (int a, int b) {
    if (d[a]>d[b]) return find_lca(b,a);
    int dif = d[b]-d[a], step = 0;
    while (dif>0) {
        if (dif%2) b = st[b][step];
        dif/=2, step++;
    }
    if (a==b) return a;
    for (int i = 13; i >= 0; --i) {
        int anc_a = st[a][i], anc_b = st[b][i];
        if (anc_a!=anc_b) a = anc_a, b = anc_b;
    }
    return (st[a][0]);
}

set<int> solve (int u, int prev) {
    set<int> ids;
    for (ii vid : neibs[u]) {
        int v = vid.fi, id = vid.se;
        if (v!=prev) {
            set<int> get = solve(v, u);
            if ((int)get.size()>=k) ans.pb(id);
            merge(all(ids), all(get), inserter(ids, ids.begin()));
        }
    }
    for (int id : nodes_ids[u]) ids.insert(id);
    for (int id : del_ids[u]) ids.erase(id);
    return ids;
}

int main() {    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int m;
    cin >> n >> m >> k;

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

    dfs (1,1,0);
    complete_st ();

    rep (m) {
        int s; cin >> s;
        int anc, ss[s];
        rep2 (s) cin >> ss[j];
        anc = ss[s-1];
        rep2 (s-1) anc = find_lca (anc, ss[j]);
        del_ids[anc].pb(i+1);
        rep2 (s) nodes_ids[ss[j]].pb(i+1);
   }
    
    solve (1, 1);
    
    cout << ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for (int a : ans) cout << a << " ";
    cout << "\n";
}

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