| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 412487 | 20160161simone | Race (IOI11_race) | C++14 | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
char c=getchar();bool flag=0;ll x=0;
while(c<'0'||c>'9'){if(c=='-')flag=1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return flag?-x:x;
}
const ll N=2e5+10;
struct edge{
ll to,nxt,w;
}ln[N*2];
ll idx[N],topln;
void add_edge(ll u,ll v,ll w){
ln[++topln]=(edge){v,idx[u],w},idx[u]=topln;
ln[++topln]=(edge){u,idx[v],w},idx[v]=topln;
}
ll k;
ll S,rt,rtmx,vis[N],siz[N];
void init(ll x){S=x,rt=0,rtmx=N;}
void findrt(ll x,ll fa){
ll mx=0; siz[x]=1;
for(ll i=idx[x];i;i=ln[i].nxt){
if(ln[i].to==fa || vis[ln[i].to]) continue;
findrt(ln[i].to,x);
siz[x]+=siz[ln[i].to];
mx=max(mx,siz[ln[i].to]);
}
mx=max(mx,S-siz[x]);
if(mx<rtmx) mx=rtmx,rt=x;
}
const ll K=1e6+10;
ll ans=N,dis[N],top=0,cnt[K];
struct node{
ll w,d;
}mrk[N];
ll mrk2[N];
void Count(ll x,ll fa,ll d){
if(dis[x]>k || d>=ans) return;
mrk[++top]=(node){dis[x],d};
for(ll i=idx[x];i;i=ln[i].nxt){
if(ln[i].to==fa || vis[ln[i].to]) continue;
dis[ln[i].to]=dis[x]+ln[i].w;
Count(ln[i].to,x,d+1);
}
}
void solve(ll x){
ll top2=0;
cnt[0]=0;
for(ll i=idx[x];i;i=ln[i].nxt){
if(vis[ln[i].to]) continue;
top=0;
dis[ln[i].to]=ln[i].w,Count(ln[i].to,x,1);
for(ll j=1;j<=top;j++)
if(cnt[k-mrk[j].w]!=cnt[K-1]){
ans=min(ans,mrk[j].d+cnt[k-mrk[j].w]);
}
for(ll j=1;j<=top;j++){
cnt[mrk[j].w]=min(cnt[mrk[j].w],mrk[j].d);
mrk2[++top2]=mrk[j].w;
}
}
for(ll i=1;i<=top2;i++) cnt[mrk2[i]]=cnt[K-1];
}
void dfs(ll x){
vis[x]=1;
solve(x);
for(ll i=idx[x];i;i=ln[i].nxt){
if(vis[ln[i].to]) continue;
init(siz[ln[i].to]),findrt(ln[i].to,0);
dfs(rt);
}
}
int main(){
memset(cnt,127,sizeof(cnt));
ll n=read();
k=read();
for(ll i=1;i<n;i++){
ll u=read()+1,v=read()+1,w=read();
add_edge(u,v,w);
}
init(n),findrt(1,0);
dfs(1);
if(ans==N) printf("-1\n");
else printf("%lld\n",ans);
}