oj.uz

답안 #1004478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004478 2024-06-21T09:19:26 Z coolboy19521 Railway (BOI17_railway) C++17
0 / 100
 55 ms 29524 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 29524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 23968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 23968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -