Submission #1253914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253914		ankite	Railway (BOI17_railway)	C++20	100 / 100	104 ms	22984 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int li = 1e5 + 5;
struct edge{ int v, id; };

int n, m, k, tin[li], tout[li], tick = 0, anc[li][21], p_edge[li];
vector<edge> adj[li];

void dfs(int node = 1, int par = 0) {
    tin[node] = ++tick;
    for (int i=1; i<=19; i++) anc[node][i] = anc[anc[node][i-1]][i-1];

    for (edge& other : adj[node]) {
        if (other.v == par) continue;
        anc[other.v][0] = node;
        p_edge[other.v] = other.id;
        dfs(other.v, node);
    }

    tout[node] = tick;
}

bool is_anc(int a, int b) { return (tin[b] >= tin[a]  &&  tout[b] <= tout[a]); }

int lca(int a, int b) {
    if (is_anc(a, b)) return a;

    for (int i=19; ~i; i--) if (anc[a][i]  &&  !is_anc(anc[a][i], b)) a = anc[a][i];
    return anc[a][0];
}

int fen[li];
void update(int pos, int val) { for (; pos <= n; pos += pos & (-pos)) fen[pos] += val; }
int query(int pos) { int ans = 0; for(;pos; pos -= pos & (-pos)) ans += fen[pos]; return ans; }
int get(int l, int r) { return query(r) - query(l - 1); }

int chosen[li];

signed main() {
    cin >> n >> m >> k;
    for (int i=1, u, v; i<=n-1; i++) {
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    dfs();
    while (m--) {
        int s;
        cin >> s;
        for (int i=1; i<=s; i++) cin >> chosen[i];

        sort(chosen + 1, chosen + s + 1, [](int x, int y) { return tin[x] < tin[y]; });

        chosen[s + 1] = chosen[1];
        for (int i=1; i<=s; i++) {
            int l = lca(chosen[i], chosen[i + 1]);
            update(tin[chosen[i]], 1);
            update(tin[chosen[i + 1]], 1);
            update(tin[l], -2);
        }
    }
    vector<int> ans;
    k <<= 1;
    for (int i=2; i<=n; i++) {
        if (get(tin[i], tout[i]) >= k) ans.push_back(p_edge[i]);
    }

    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
}

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