#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e6+1;
int n,k,sz[N],len[N],mx = 0,ans = 1e9;
vector<pii>adj[N];
bool del[N];
int dfs(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(v.fi == p || del[v.fi]) continue;
sz[u] += dfs(v.fi,u);
}
return sz[u];
}
int get_centroid(int u, int p, int con){
for(auto v : adj[u])
if(v.fi != p && !del[v.fi] && sz[v.fi] > con/2) return get_centroid(v.fi,u,con);
return u;
}
void dem(int u, int p, bool type, int h, int cc = 1){
if(h > k) return;
mx = max(mx,h);
if(type) len[h] = min(len[h],cc);
else ans = min(ans,cc+len[k-h]);
//cout << u << " " << p << " " << h << "\n";
for(auto v : adj[u])
if(v.fi != p && !del[v.fi]) dem(v.fi,u,type,h+v.se,cc+1);
}
void cd(int u){
int centroid = get_centroid(u,-1,dfs(u,-1));
del[centroid] = true;
len[0] = 0;
mx = 0;
for(auto v : adj[centroid]){
if(!del[v.fi]){
dem(v.fi,centroid,0,v.se);
dem(v.fi,centroid,1,v.se);
}
}
fill(len,len+mx+1,1e9);
for(auto v : adj[centroid]) if(!del[v.fi]) cd(v.fi);
}
int best_path(int N, int K, int h[][2], int l[]) {
n = N, k = K;
for(int i = 0; i < n - 1; i++){
adj[h[i][1]].push_back({h[i][2], l[i]});
adj[h[i][2]].push_back({h[i][1], l[i]});
}
for(int i = 0; i <= 2000000; i++) len[i] = 1e9;
cd(0);
if(ans == 1e9) cout << -1;
else cout << ans;
}
Compilation message (stderr)
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
57 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |