Submission #543865

#TimeUsernameProblemLanguageResultExecution timeMemory
543865AJ00Race (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> //#include "race.h" using namespace std; //#define ll long long #define ll long long const ll MAXN = 200001; const ll LOGN = 20; vector<vector<pair<ll,ll>>> adj(MAXN); int depth[MAXN]; ll par[MAXN][LOGN],weight[MAXN][LOGN]; pair<ll,int> lca(ll x, ll y){ ll X = x, Y = y; if (depth[X] < depth[Y]){ swap(x,y); swap(X,Y); } ll dh = depth[x]-depth[y]; ll totw = 0; for (ll i = LOGN-1; i >= 0; i--){ if (dh&(1<<i)){ totw += weight[x][i]; x = par[x][i]; } } if (x == y){ return {totw, depth[X]-depth[Y]}; } int lvl = 0; for (ll i = LOGN; i >= 0; i--){ if (par[x][i] != par[y][i]){ totw += weight[x][i]; totw += weight[y][i]; lvl += (1<<i); x = par[x][i]; y = par[y][i]; } } totw += weight[x][0]; totw += weight[y][0]; lvl += 1; lvl *= 2; return {totw,lvl+depth[X]-depth[Y]}; } void dfs(ll x, ll h = 0, ll p= 0, ll w = 0){ depth[x] = h; par[x][0] = p; weight[x][0] = w; for (ll i = 1; i < LOGN; i++){ par[x][i] = par[par[x][i-1]][i-1]; weight[x][i] = weight[x][i-1] + weight[par[x][i-1]][i-1]; } for (auto ch: adj[x]){ ll t = ch.first; ll wt = ch.second; if (t != p){ dfs(t,h+1,x,wt); } } } int best_path(ll N,ll K,ll H[][2],ll L[]){ for (ll i = 0; i < N-1; i++){ adj[H[i][0]].push_back({H[i][1],L[i]}); adj[H[i][1]].push_back({H[i][0],L[i]}); } dfs(0); int ans = N; for (ll i = 0; i < N; i++){ for (ll j = i+1; j < N; j++){ pair<ll,int> l = lca(i,j); if (l.first == K){ // cout << i << " " << j << " " << depth[i] << " " << depth[j] << "\n"; ans = min(ans,l.second); } } } ans -= (ans == N ? N+1 : 0); return ans; }

Compilation message (stderr)

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