Submission #1264434

#TimeUsernameProblemLanguageResultExecution timeMemory
1264434piolkRace (IOI11_race)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<pair<int,int>>> tree; vector<int> subSizes; vector<bool> removed; int K; int ans=INT_MAX; int getSubSize(int node,int parent){ subSizes[node]=1; for (auto [child,cost]:tree[node]){ if (child==parent || removed[child]) continue; subSizes[node]+=getSubSize(child,node); } return subSizes[node]; } int getCentroid(int node,int parent,int subSize){ for (auto [child,cost]:tree[node]){ if (child==parent || removed[child]) continue; if (subSizes[child]*2>subSize) return getCentroid(child,node,subSize); } return node; } void getPaths(int node,int parent,int centroid,int dist,int edges,vector<pair<int,int>> &distances){ if (dist>K) return; distances.emplace_back(dist,edges); for (auto [child,cost]:tree[node]){ if (child==parent || removed[child]) continue; getPaths(child,node,centroid,dist+cost,edges+1,distances); } } void process(int centroid){ vector<int> dists(K+7); //sum, edges for (auto [child,cost]:tree[centroid]){ if (removed[child]) continue; // potrzebuje wszystkie sciezki vector<pair<int,int>> distances; getPaths(child,centroid,centroid,cost,1,distances); for (auto [sum,edges]:distances){ if (dists[K-sum]>0){ ans=min(ans,dists[K-sum]+edges); } } for (auto [sum,edges]:distances){ if (dists[sum]==0) dists[sum]=edges; else dists[sum]=min(dists[sum],edges); } } } void decomp(int node){ int centroid=getCentroid(node,-1,getSubSize(node,-1)); process(centroid); removed[centroid]=true; for (auto [child,cost]:tree[centroid]){ if (removed[child]) continue; decomp(child); } } int best_path(int n,int k,int h[][2],vector<int> l){ ans=INT_MAX; K=k; tree.clear(); subSizes.clear(); removed.clear(); tree.resize(n+1); subSizes.resize(n+1); removed.resize(n+1); for (int i=0;i<n-1;i++){ int u=h[i][0]; int v=h[i][1]; int price=l[i]; tree[u].emplace_back(v,price); tree[v].emplace_back(u,price); } decomp(1); return (ans!=INT_MAX ? ans : -1); }

Compilation message (stderr)

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