Submission #1194056

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

race

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

vector<vector<pair<int, int>>> tree;
vector<int> sub;
vector<bool> del;
int n, k;
int ans = -1;
map<ll, int> cnt;

void calc_subs(int node, int par) {
    sub[node] = 1;
    for (auto [next, w]: tree[node]) {
        if (del[next] || next == par) continue;
        calc_subs(next, node);
        sub[node] += sub[next];
    }
}

int find_centroid(int node, int tot, int par = 0) {
    for (auto [next, w]: tree[node]) {
        if (del[next] || next == par) continue;
        if (sub[next] * 2 >= tot) return find_centroid(next, tot, node);
    }
    return node;
}

void add(int node, int par, ll totLen, int dep = 1) {
    if (!cnt[totLen]) {
        cnt[totLen] = dep;
    }
    else cnt[totLen] = min(cnt[totLen], dep);
    for (auto [next, w]: tree[node]) {
        if (next == par || del[next]) continue;
        add(next, node, totLen + w, dep+1);
    }
}

void find_ans(int node, int par, ll totLen, int dep = 1) {
    ll need = k - totLen;
    if (need == 0) {
        if (ans == -1) ans = dep;
        else ans = min(ans, dep);
    }
    if (need > 0 && cnt[need]) {
        if (ans == -1) ans = cnt[need] + dep;
        else ans = min(ans, cnt[need] + dep);
    }
    for (auto [next, w]: tree[node]) {
        if (next == par || del[next]) continue;
        find_ans(next, node, totLen + w, dep+1);
    }
}

void build(int node) {
    calc_subs(node, 0);
    int cd = find_centroid(node, sub[node]);
    cnt.clear();
    for (auto [next, w]: tree[cd]) {
        if (del[next]) continue;
        find_ans(next, cd, w);
        add(next, cd, w);
    }
    cnt.clear();
    del[cd] = true;
    for (auto [next, w]: tree[cd]) {
        if (del[next]) continue;
        build(next);
    }
}

int best_path(int N, int K, vector<vector<int>> H, vector<int> L) {
    n = N;
    k = K;
    tree.resize(n+1);
    del.assign(n+1, false);
    sub.assign(n+1, 0);
    for (int i = 0; i < n-1; i++) {
        H[i][0]++;
        H[i][1]++;
        tree[H[i][0]].push_back({H[i][1], L[i]});
        tree[H[i][1]].push_back({H[i][0], L[i]});
    }
    build(1);
    if (ans != -1) ans++;
    return ans;
}
/*
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << best_path(3, 3, {{0, 1}, {0, 2}, {}}) << "\n";
}*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccwbHVl3.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