Submission #333064

#	Time	Username	Problem	Language	Result	Execution time	Memory
333064		OttoTheDino	Railway (BOI17_railway)	C++17	23 / 100	137 ms	29284 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, ord[mxn], d[mxn], st[mxn][14], cnt[mxn], o;
vi nodes_ids[mxn], ans;

bool compare (int a, int b) {
    if (ord[a]<ord[b]) return 1;
    return 0;
}

void dfs (int u, int prev, int depth) {
    st[u][0] = prev, d[u] = depth, ord[u] = o++;
    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]);
}

void solve (int u, int prev) {
    for (ii vid : neibs[u]) {
        int v = vid.fi;
        if (v != prev) {
            solve (v, u);
            cnt[u] += cnt[v];       
        }
    }
}

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

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

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

    rep (m) {
        int s; cin >> s;
        int nodes[s];
        rep2 (s) cin >> nodes[j];
        sort(nodes, nodes+s, compare);
        rep2 (s) {
            cnt[find_lca(nodes[j], nodes[(j+1)%s])]--;
            cnt[nodes[j]]++;
        }
   }
    
    solve (1, 1);

    rep (n-1) {
        if (ord[edge[i].fi]<ord[edge[i].se]) {
            if (cnt[edge[i].se] >= k)
                ans.pb(i+1);
        }
        else if (cnt[edge[i].fi] >= k)
            ans.pb(i+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