Submission #1204915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204915		minhpk	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b;
vector<pair<int, int>> z[1000005];
int del[1000005], child[1000005], sz;
int cnt1[1000005], cnt[1000005];
int min1 = 1e16;
vector<int> v;

void predfs(int i, int par) {
    child[i] = 1;
    for (auto p : z[i]) {
        if (p.first == par || del[p.first]) continue;
        predfs(p.first, i);
        child[i] += child[p.first];
    }
}

int centroid(int i, int par) {
    for (auto p : z[i]) {
        if (p.first == par || del[p.first]) continue;
        if (child[p.first] > sz / 2) return centroid(p.first, i);
    }
    return i;
}

void dfs(int i, int par, int val, int len) {
    if (val > b) return;
    if (cnt[b - val] || val == b) min1 = min(min1, len + cnt[b - val]);
    if (cnt1[val] == 0 || cnt1[val] > len) {
        v.push_back(val);
        cnt1[val] = len;
    }
    for (auto p : z[i]) {
        if (p.first == par || del[p.first]) continue;
        dfs(p.first, i, val + p.second, len + 1);
    }
}

void skibidi(int i) {
    for (int x : v){
            cnt1[x] = 0;  
            cnt[x]=0;
    }
    v.clear();
    cnt[0] = 0;

    for (auto p : z[i]) {
        if (del[p.first]) continue;
        dfs(p.first, i, p.second, 1);
        for (int x : v) cnt[x] = min(cnt[x] ? cnt[x] : LLONG_MAX, cnt1[x]);
    }
}

void decompose(int i) {
    predfs(i, 0);
    sz = child[i];
    i = centroid(i, 0);
    del[i] = 1;
    skibidi(i);

    for (auto p : z[i]) {
        if (del[p.first]) continue;
        decompose(p.first);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i = 1; i < a; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        z[x].push_back({y, t});
        z[y].push_back({x, t});
    }
    decompose(1);
    cout << (min1 == 1e16 ? -1 : min1);
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccdHJRUC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccviwUVQ.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccdHJRUC.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status