| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1202170 | namhh | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#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 main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i = 1; i < n; i++){
int u,v,c;
cin >> u >> v >> c;
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
for(int i = 0; i <= 2000000; i++) len[i] = 1e9;
cd(0);
if(ans == 1e9) cout << -1;
else cout << ans;
}