| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 680473 | tommy1024 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int inf=1e9;
int N,K;
int a,b,c;
int sz[200005],kill[200005];
int ans=inf;
vector <pii> v[200005];
map <int,int> m,tmp;
int get_sz(int x,int par){
sz[x]=1; // reset
for(auto[i,d]:v[x]){
if(i==par)continue;
if(kill[i])continue;
sz[x]+=get_sz(i,x);
}
return sz[x];
}
int get_cent(int x,int par,int c){
for(auto[i,d]:v[x]){
if(i==par)continue;
if(kill[i])continue;
if(sz[i]>c)return get_cent(i,x,c);
}
return x;
}
void sch(int x,int d,int st,int tab){ // step
if(d>K)return;
auto it=tmp.find(d);
if(it==tmp.end())tmp[d]=st;
else tmp[d]=min(tmp[d],st);
for(auto[i,D]:v[x]){
if(i==tab)continue;
if(kill[i])continue;
sch(i,d+D,st+1,x);
}
}
void update(){
for(auto[a,b]:tmp){
auto it=m.find(a);
if(it==m.end())m[a]=b;
else m[a]=min(m[a],b);
}
}
void f(int x){
int s=get_sz(x,-1); // already considered in kill[]
int ct=get_cent(x,-1,s/2);
kill[ct]=1;
for(auto[i,d]:v[ct]){
tmp.clear();
sch(i,d,1,x);
for(auto[a,b]:tmp){
auto it=m.find(K-a);
if(it!=m.end()){
ans=min(ans,m[K-a]+b);
//printf("[%d %d]",m[K-a],b);
}
}
update();
}
m.clear();
m[0]=0;
for(auto[i,d]:v[ct]){
if(kill[i])continue;
f(i);
}
kill[ct]=0;
}
int main()
{
scanf("%d%d",&N,&K);
for(int i=1;i<=N-1;i++){
scanf("%d%d%d",&a,&b,&c);
v[a].push_back({b,c});
v[b].push_back({a,c});
}
m[0]=0;
f(0);
if(ans==inf)ans=-1;
printf("%d",ans);
return 0;
}