Submission #1254343

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

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int oo = 1e18;
const int N = 200005;

int mix = oo;
vector<pair<int, int>> a[N];

struct Centroid {
    int sz[N], high[N], len[N];
    bool cen[N];
    map<int, int> mp;

    void DFS(int u, int par) {
        sz[u] = 1;
        for (auto [v, w] : a[u]) {
            if (v == par || cen[v]) continue;
            DFS(v, u);
            sz[u] += sz[v];
        }
    }

    int find_centroid(int u, int par, int total) {
        for (auto [v, w] : a[u]) {
            if (v == par || cen[v]) continue;
            if (sz[v] > total / 2) return find_centroid(v, u, total);
        }
        return u;
    }

    void DFS_ANS(int u, int par, bool check) {
        if (high[u] > k) return;

        if (check) {
            if (mp.count(k - high[u])) {
                mix = min(mix, mp[k - high[u]] + len[u]);
            }
        } else {
            if (!mp.count(high[u])) {
                mp[high[u]] = len[u];
            } else {
                mp[high[u]] = min(mp[high[u]], len[u]);
            }
        }

        for (auto [v, w] : a[u]) {
            if (v == par || cen[v]) continue;
            len[v] = len[u] + 1;
            high[v] = high[u] + w;
            DFS_ANS(v, u, check);
        }
    }

    void decompose(int u) {
        DFS(u, -1);
        int centroid = find_centroid(u, -1, sz[u]);
        cen[centroid] = true;

        mp.clear();
        mp[0] = 0;
        high[centroid] = 0;
        len[centroid] = 0;

        for (auto [v, w] : a[centroid]) {
            if (cen[v]) continue;
            high[v] = w;
            len[v] = 1;
            DFS_ANS(v, centroid, true);
            DFS_ANS(v, centroid, false);
        }

        for (auto [v, w] : a[centroid]) {
            if (!cen[v]) decompose(v);
        }
    }

    int k;
    void solve(int K) {
        k = K;
        decompose(1);
    }
};

Centroid Cen;

int best_path(int N, int K, int H[][2], int L[]) {
    // Clear previous test case data
    for (int i = 0; i <= N; ++i) {
        a[i].clear();
        Cen.sz[i] = Cen.high[i] = Cen.len[i] = 0;
        Cen.cen[i] = false;
    }

    mix = oo;

    for (int i = 0; i < N - 1; ++i) {
        int u = H[i][0] + 1;
        int v = H[i][1] + 1;
        int c = L[i];
        a[u].emplace_back(v, c);
        a[v].emplace_back(u, c);
    }

    Cen.solve(K);

    return (mix == oo ? -1 : mix);
}

Compilation message (stderr)

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