Submission #1146848

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

race

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

#define F first
#define S second
#define PB push_back
#define MP make_pair

using ll = long long;
using pi = pair<int, int>;

template<typename T>
using vec = vector<T>;

template<typename T, const unsigned int N>
using arr = array<T, N>;

const int INF = 1e9 + 7;

int n, k, mx = 1e6, ans = INF;
int sz[100005], mn[1000005];
bool dead[100005];
vec<pi> adj[100005];

int pre_dfs(int u, int p)
{
    sz[u] = 1;
    for (auto v : adj[u])
        if (v.F != p && !dead[v.F])
            sz[u] += pre_dfs(v.F, u);
    return sz[u];
}

int find_centroid(int u, int p, int ts)
{
    for (auto v : adj[u])
        if (v.F != p && !dead[v.F] && sz[v.F] * 2 > ts)
            return find_centroid(v.F, u, ts);
    return u;
}

void dfs(int u, int p, int s, int d, bool f)
{
    if (s > k)
        return;
    mx = max(mx, d);
    if (f)
        mn[s] = min(mn[s], d);
    else {
        cout << k - s << ' ' << mn[k - s] << '\n';
        ans = min(ans, mn[k - s] + d);
    }

    for (auto v : adj[u])
        if (v.F != p && !dead[v.F])
            dfs(v.F, u, s + v.S, d + 1, f);
}

void solve(int u)
{
    int c = find_centroid(u, -1, pre_dfs(u, -1));
    dead[c] = 1;

    fill(mn, mn + mx + 1, INF);

    mx = 0;
    for (auto v : adj[c])
        if (!dead[v.F])
        {
            dfs(v.F, c, v.S, 1, 0);
            dfs(v.F, c, v.S, 1, 1);
        }

    for (auto v : adj[c])
        if (!dead[v.F])
            solve(v.F);
}

int best_path(int N, int K, vec<vec<int>> H, vec<int> L)
{
    n = N, k = K;
    for (int i = 0; i < N - 1; i++)
    {
        adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
        adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
    }

    solve(1);
    return (ans == INF ? -1 : ans);
}

Compilation message (stderr)

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