Submission #1222050

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

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int, int>
#define all(a) (a).begin(), (a).end()
 
const int N = 2e5 + 5;
vector<pair<int, int>> g[N];
int sz[N], is_removed[N];
int k, ans = 1e10, n;
map<int, int> cnt;
int get_sz(int u, int p)
{
    sz[u] = 1;
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        sz[u] += get_sz(v, u);
    }
    return sz[u];
}
 
int get_cent(int u, int p, int cur_sz)
{
    for (auto [v, _] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        if (sz[v] * 2 > cur_sz)
            return get_cent(v, u, cur_sz);
    }
    return u;
}
void dfs(int v, int p, int depth, int delta, int w)
{
    if(cnt.count(w))    
        cnt[w] = min(cnt[w], depth);
    else cnt[w] = depth;
    for (auto [u, W] : g[v])
    {
        if (u == p || is_removed[u])
            continue;
        dfs(u, v, depth + 1, delta, w + W);
    }
}
void get_ans(int u, int p, int depth, int w)
{
    if (k - w >= 0 && cnt.count(k - w))
        ans = min(ans, cnt[k - w] + depth);
    for (auto [v, W] : g[u])
    {
        if (v == p || is_removed[v])
            continue;
        get_ans(v, u, depth + 1, W + w);
    }
}
 
void comp(int v)
{
    int size = get_sz(v, -1), cent = get_cent(v, -1, size);
    cnt[0] = 0;
    for (auto [u, w] : g[cent])
    {
        if (is_removed[u])
            continue;
        get_ans(u, cent, 1, w);
        dfs(u, cent, 1, 1, w);
    }
    cnt.clear();
    is_removed[cent] = 1;
    for (auto [u, _] : g[cent])
    {
        if (is_removed[u])
            continue;
        comp(u);
    }
}
 
// int32_t main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//     cin >> n >> k;
//     for(int i = 0; i < n - 1; i++){
//         int u, v, w; cin >> u >> v >> w;
//         g[u].push_back({v, w});
//         g[v].push_back({u, w});
//     }
//     comp(0);
//     cout << ans;
//     return 0;
// }

int best_path(int nn, int kk, int h[][2], int l[]){
    n = nn; k = kk;
    for(int i =0 ; i < n - 1; i++){
        g[h[i][0]].push_back({h[i][1], l[i]});
        g[h[i][1]].push_back({h[i][0], l[i]});
    }
    comp(0);
    return ans == 1e10 ? -1 : ans;
}

Compilation message (stderr)

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