Submission #1053860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053860		ArthuroWich	Railway (BOI17_railway)	C++17	100 / 100	89 ms	37308 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define int long long int
vector<pair<int, int>> adj[100005];
int succ[100005][20], from[100005], dep[100005], st[100005], en[100005], seg[4*100005], timer = 0;
void update(int n, int l, int r, int i, int v) {
    if (l == r) {
        seg[n] += v;
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            update(2*n, l, m, i, v);
        } else {
            update(2*n+1, m+1, r, i, v);
        }
        seg[n] = seg[2*n] + seg[2*n+1];
    }
}
int query(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return 0;
    } else if (a <= l && r <= b) {
        return seg[n];
    } else {
        int m = (l+r)/2;
        return query(2*n, l, m, a, b)+query(2*n+1, m+1, r, a, b);
    }
}
void dfs(int i, int p) {
    st[i] = timer;
    timer++;
    for (auto [j, ind] : adj[i]) {
        if (j == p) {
            from[i] = ind;
            continue;
        }
        dep[j] = dep[i]+1;
        succ[j][0] = i;
        dfs(j, i);
    }
    en[i] = timer;
}
void initsucc(int n) {
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            succ[i][j] = succ[succ[i][j-1]][j-1];
        }
    }
}
int kthjump(int a, int k) {
    for (int j = 0; j < 20; j++) {
        if (k & (1 << j)) {
            a = succ[a][j];
        }
    }
    return a;
}
int lca(int a, int b) {
    if (dep[a] > dep[b]) {
        swap(a, b);
    }
    b = kthjump(b, dep[b]-dep[a]);
    if (a == b) {
        return a;
    }
    for (int j = 19; j >= 0; j--) {
        if (succ[a][j] != succ[b][j]) {
            a = succ[a][j];
            b = succ[b][j];
        }
    }
    return succ[a][0];
}
bool cmp(int a, int b) {
    return st[a] < st[b];
}
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, -1);
    initsucc(n);
    while(m--) {
        int c, l;
        cin >> c;
        vector<int> a(c);
        for (int &x : a) {
            cin >> x;
        }
        sort(a.begin(), a.end(), cmp);
        a.push_back(a[0]);
        for (int i = 0; i < c; i++) {
            l = lca(a[i], a[i+1]);
            update(1, 0, n-1, st[a[i]], 1);
            update(1, 0, n-1, st[a[i+1]], 1);
            update(1, 0, n-1, st[l], -2);
        }
    }
    vector<int> ans;
    for (int i = 2; i <= n; i++) {
        if (query(1, 0, n-1, st[i], en[i]-1) >= 2*k) {
            ans.push_back(from[i]);
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i : ans) {
        cout << i << " ";
    }
    cout << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

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