Submission #1004492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004492		coolboy19521	Railway (BOI17_railway)	C++17	0 / 100	50 ms	29524 KiB

railway

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 1e5 + 5;
const int sm = 25;

vector<vector<int>> aj[sz];
int mp[sz], mn[sz];
int up[sm][sz];
vector<int> r;
int dp[sz];
int k;

void dfs1(int v, int p = 0, int d = 1) {
    up[0][v] = p;
    dp[v] = d;
    for (auto& u : aj[v]) {
        int to = u[0];
        if (to != p) {
            dfs1(to, v, d + 1);
        }
    }
}

void dfs2(int v, int p = 0, int s = 0) {
    s += mp[v];
    s -= mn[v];
    
    for (auto& u : aj[v]) {
        int to = u[0];
        int nm = u[1];
        if (to != p) {
            if (s == k) {
                r.push_back(nm);
            }
            dfs2(to, v, s);
        }
    }
}

int lca(int a, int b) {
    if (dp[a] > dp[b]) swap(a, b);
    int d = dp[b] - dp[a];
    for (int i = 0; i < sm; i ++) {
        if (d & (1ll << i)) {
            b = up[i][b];
        }
    }
    if (a == b) return a;
    for (int i = sm - 1; -1 < i; i --) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m >> k;

    for (int i = 1; i <= n - 1; i ++) {
        int a, b;
        cin >> a >> b;

        aj[a].push_back({b, i});
        aj[b].push_back({a, i});
    }

    dfs1(1);

    for (int i = 1; i <= m; i ++) {
        int s, a, b;
        cin >> s >> a >> b;
        int l = lca(a, b);
        mp[l] ++;
        mn[a] ++;
        mn[b] ++;
    }

    dfs2(1);

    cout << r.size() << '\n';

    for (int i : r) {
        cout << i << ' ';
    }
}

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