Submission #1115823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115823		vjudge1	Railway (BOI17_railway)	C++17	100 / 100	97 ms	23748 KiB

railway

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