Submission #757650

#	Time	Username	Problem	Language	Result	Execution time	Memory
757650		adaawf	Railway (BOI17_railway)	C++14	100 / 100	129 ms	23696 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> g[100005];
vector<int> res;
int k, c[100005], pp[100005][20], d[100005], dd[100005], a[200005], z = 0;
void dfs(int x, int p) {
    pp[x][0] = p;
    for (int i = 1; i < 20; i++) {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
    }
    d[x] = d[p] + 1;
    dd[x] = ++z;
    for (auto w : g[x]) {
        if (w.first == p) continue;
        dfs(w.first, x);
    }
}
int dfs2(int x, int p, int y) {
    for (auto w : g[x]) {
        if (w.first == p) continue;
        c[x] += dfs2(w.first, x, w.second);
    }
    if (c[x] >= k * 2 && y != 0) {
        res.push_back(y);
    }
    return c[x];
}
int lca(int x, int y) {
    int k = 19;
    if (d[x] < d[y]) swap(x, y);
    while (k >= 0 && d[x] > d[y]) {
        if (d[pp[x][k]] >= d[y]) {
            x = pp[x][k];
        }
        k--;
    }
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (pp[x][i] != pp[y][i]) {
            x = pp[x][i];
            y = pp[y][i];
        }
    }
    return pp[x][0];
}
bool cmp(int aa, int bb) {
    return dd[aa] < dd[bb];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1, cmp);
        a[n + 1] = a[1];
        for (int i = 1; i <= n; i++) {
            c[a[i]]++;
            c[a[i + 1]]++;
            c[lca(a[i], a[i + 1])] -= 2;
        }
    }
    dfs2(1, 0, 0);
    cout << res.size() << '\n';
    sort(res.begin(), res.end());
    for (int w : res) {
        cout << w << " ";
    }
}

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