Submission #1268828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268828		bgnbvnbv	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 INF = 1e18;
const int MAXN = 200005;

vector<pair<int,int>> adj[MAXN];
int sz[MAXN];
bool removed[MAXN];
int ans;
int N_global, K_global;

int dfs_size(int u,int p){
    sz[u] = 1;
    for(auto [v,w] : adj[u]){
        if(!removed[v] && v != p) sz[u] += dfs_size(v,u);
    }
    return sz[u];
}

int dfs_cen(int u, int p, int n){
    for(auto [v,w] : adj[u]){
        if(!removed[v] && v != p){
            if(sz[v] > n / 2) return dfs_cen(v,u,n);
        }
    }
    return u;
}

void dfs_collect(int u,int p, long long dist, int d ,vector<pair<long long,int>> &path){
    if(dist > K_global) return;
    path.push_back({dist,d});
    for(auto [v,w] : adj[u]){
        if(!removed[v] && v != p){
            dfs_collect(v,u,dist+w,d+1,path);
        }
    }
}

void solve(int root){
    int n = dfs_size(root,-1);
    int c = dfs_cen(root,-1,n);

    unordered_map<long long,int> best;
    best[0] = 0;

    for(auto [v,w] : adj[c]){
        if(removed[v]) continue;
        vector<pair<long long,int>> path;
        dfs_collect(v,c,w,1,path);

        for(auto [dist, d] : path){
            if(dist == K_global) ans = min(ans,d);
            if(best.count(K_global - dist)){
                ans = min(ans,d + best[K_global - dist]);
            }
        }

        for(auto [dist, d] : path){
            if(!best.count(dist)) best[dist] = d;
            else best[dist] = min(best[dist],d);
        }
    }

    removed[c] = true;
    for(auto [v,w] : adj[c]){
        if(!removed[v]) solve(v);
    }
}

int best_path(int N,int K,int H[][2], int L[]){
    N_global = N; K_global = K;
    for(int i=0;i<N;++i){
        adj[i].clear();
        removed[i] = false;
    }
    ans = INF;

    for(int i=0;i<N-1;++i){
        int u = H[i][0], v = H[i][1], w = L[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

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

Compilation message (stderr)

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