Submission #1304044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304044		mocha	Railway (BOI17_railway)	C++20	100 / 100	147 ms	22440 KiB

railway

#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int mx = 1e5+5;

int n, m, k;
vector<pair<int, int>> g[mx];
int pid[mx];
int pr[20][mx];
int dfn[mx];
int dep[mx];
int a[mx];
int sz;

void dfs(int x, int p) {
    dfn[x] = ++sz;
    dep[x] = dep[p]+1;
    pr[0][x] = p;
    for (auto [v, id]:g[x]) {
        if (v == p) continue;
        pid[v] = id;
        dfs(v, x);
    }
}

bool cmp(int x, int y) {
    return dfn[x] < dfn[y];
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    int d = dep[y] - dep[x];
    for (int i=19;~i;i--) {
        if (d & (1<<i)) y = pr[i][y];
    }
    if (x == y) return x;
    for (int i=19;~i;i--) {
        if (pr[i][x] != pr[i][y]) {
            x = pr[i][x];
            y = pr[i][y];
        }
    }
    return pr[0][x];
}

vector<int> ans;

void dfs2(int x, int p) {
    for (auto [i, id]:g[x]) {
        if (i == p) continue;
        dfs2(i, x);
        a[x] += a[i];
    }
    if (a[x] >= 2*k) {
        ans.push_back(pid[x]);
    }
}

signed main() {
    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<20;i++) {
        for (int j=1;j<=n;j++) {
            pr[i][j] = pr[i-1][pr[i-1][j]];
        }
    }
    // for (int i=1;i<=n;i++) {
    //     cout << dfn[i] << " ";
    // }
    // cout << "owo\n";
    for (int i=1;i<=m;i++) {
        int x;
        cin >> x;
        vector<int> ve;
        for (int j=1;j<=x;j++) {
            int y;
            cin >> y;
            ve.push_back(y);
        }
        sort(ve.begin(), ve.end(), cmp);
        ve.push_back(ve[0]);
        for (int i=0;i+1<ve.size();i++) {
            a[ve[i]]++;
            a[ve[i+1]]++;
            a[lca(ve[i], ve[i+1])]-=2;
        }
    }
    dfs2(1, 0);
    cout << ans.size() << "\n";
    sort(ans.begin(), ans.end());
    for (int i:ans) {
        cout << i << " ";
    }
    cout << "\n";
}

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