#include<bits/stdc++.h>
#include"race.h"
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int best_path(int n,int k,vector<vector<int>>h,vector<int>l){
vector<vector<pair<int,int>>>adj(n);
for(int i=0;i<h.size();i++){
adj[h[i][0]].pb({h[i][1],l[i]});
adj[h[i][1]].pb({h[i][0],l[i]});
}
vector<int>vis(n),sub(n);
auto dfs=[&](int node,int p,auto&& dfs)->void{
sub[node]=1;
for(auto i:adj[node]){
if(vis[i.ff] || i.ff==p)continue;
dfs(i.ff,node,dfs);
sub[node]+=sub[i.ff];
}
return;
};
vector<int>cnt(k+1,-1);
auto dfs2=[&](int node,int p,int dep,int len,vector<pair<int,int>>&depths,auto&& dfs2)->void{
depths.pb({len,dep});
for(auto i:adj[node]){
if(vis[i.ff] || i.ff==p)continue;
dfs2(i.ff,node,dep+1,len+i.ss,depths,dfs2);
}
return;
};
auto get_centroid=[&](int node)->int{
bool end=false;
int p=-1,sz=sub[node];
while(!end){
end=true;
for(auto i:adj[node]){
if(vis[i.ff] || i.ff==p || sub[i.ff]<=sz/2)continue;
p=node;
node=i.ff;
end=false;
}
}
return node;
};
int ans=2e9;
auto calc=[&](int node,auto&& calc)->void{
vis[node]=1;
vector<vector<pair<int,int>>>depths;
for(auto i:adj[node]){
if(!vis[i.ff]){
depths.pb(vector<pair<int,int>>{});
dfs2(i.ff,node,1,i.ss,depths.back(),dfs2);
}
}
cnt[0]=0;
for(auto i:depths){
for(auto j:i){
if(j.ff>k)continue;
if(cnt[k-j.ff]!=-1){
ans=min(ans,j.ss+cnt[k-j.ff]);
}
}
for(auto j:i){
if(j.ff>k)continue;
if(cnt[j.ff]==-1)cnt[j.ff]=j.ss;
else cnt[j.ff]=min(cnt[j.ff],j.ss);
}
}
for(auto i:depths){
for(auto j:i){
if(j.ff>k)continue;
cnt[j.ff]=-1;
}
}
for(auto i:adj[node]){
if(vis[i.ff])continue;
dfs(i.ff,node,dfs);
int v=get_centroid(i.ff);
calc(v,calc);
}
};
int s=get_centroid(0);
calc(s,calc);
return (ans==2e9?-1:ans);
}
Compilation message
race.cpp: In function 'int best_path(int, int, std::vector<std::vector<int> >, std::vector<int>)':
race.cpp:15:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<h.size();i++){
| ~^~~~~~~~~
/usr/bin/ld: /tmp/ccdJNi4n.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
