| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 332597 | MilosMilutinovic | Race (IOI11_race) | C++11 | 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 "race.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
void ckmx(int&a,int b){a=max(a,b);}
void ckmn(int&a,int b){a=min(a,b);}
int min(int a,int b){return a>b?b:a;}
const int N=200050;
const int M=1000050;
const int inf=1e9;
vector<pair<int,int>> E[N];
void AddEdge(int u,int v,int w){E[u].pb(mp(v,w));E[v].pb(mp(u,w));}
int k;
int sz[N];
bool was[N];
void DFS(int u,int p,int& n){
n++;sz[u]=1;
for(int i=0;i<(int)E[u].size();i++)if(!was[E[u][i].first]&&E[u][i].first!=p){
DFS(E[u][i].first,u,n);sz[u]+=sz[E[u][i].first];
}
}
int Find(int u,int p,int n){
for(int i=0;i<(int)E[u].size();i++){
int v=E[u][i].first;
if(!was[v]&&v!=p&&sz[v]>n/2)return Find(v,u,n);
}
return u;
}
int FindCentroid(int u){int n=0;DFS(u,u,n);return Find(u,u,n);}
vector<pair<int,int>> all,tmp;
int ans=inf,mn[M];
void Solve(int u,int p,int dep,int len){
if(dep>k)return;
all.pb({dep,len});
tmp.pb({dep,len});
ans=min(ans,len+mn[k-dep]);
for(int i=0;i<(int)E[u].size();i++){
int v=E[u][i].first,w=E[u][i].second;
if(!was[v]&&v!=p)Solve(v,u,dep+w,len+1);
}
}
void Decompose(int u){
u=FindCentroid(u);
was[u]=1;mn[0]=0;
tmp.pb({0,0});
int i,j;
for(i=0;i<(int)E[u].size();i++){
int v=E[u][i].first,w=E[u][i].second;
if(!was[v]){
Solve(v,u,w,1);
for(j=0;j<(int)all.size();j++)ckmn(mn[all[j].first],all[j].second);
all.clear();
}
}
for(i=0;i<(int)tmp.size();i++)mn[tmp[i].first]=inf;
tmp.clear();
for(i=0;i<(int)E[u].size();i++){
int v=E[u][i].first;
if(!was[v])Decompose(v);
}
}
int best_path(int N,int K,int H[][2],int L[]){
//return -1;
int i,n=N;k=K;
for(i=0;i<n-1;i++)AddEdge(H[i][0]+1,H[i][1]+1,L[i]);
for(i=0;i<=k;i++)mn[i]=inf;
Decompose(1);
if(ans==inf)return -1;
else return ans;
}
int main(){
int n,k;scanf("%i %i",&n,&k);
int h[n][2],l[n];
for(int i=0;i<n-1;i++){
scanf("%i %i %i",&h[i][0],&h[i][1],&l[i]);
}
printf("%i",best_path(n,k,h,l));
return 0;
}