| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 933197 | vjudge1 | 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;
const int N=2e6+5;
int n,m,Q,p,q,v,rt,O,H,Ans,A[N],B[N],Qr[N],dep[N],Dep[N],Fr[N],sz[N],Msz[N];bool Vis[N];
struct Edge{int o=1,nxt[N],num[N],last[N],w[N];}U;
bool cmp(int x,int y){return dep[x]==dep[y]?Dep[x]==Dep[y]?Fr[x]<Fr[y]:Dep[x]<Dep[y]:dep[x]<dep[y];}
void Add_Edge(int t1,int t2,int t3){U.o++,U.nxt[U.o]=t2;U.last[U.o]=U.num[t1];U.num[t1]=U.o;U.w[U.o]=v;}
void Get_root(int x,int fa,int ts){
sz[x]=1;Msz[x]=0;
for(int i=U.num[x];i;i=U.last[i])if(U.nxt[i]!=fa&&!Vis[U.nxt[i]])Get_root(U.nxt[i],x,ts),sz[x]+=sz[U.nxt[i]],Msz[x]=max(Msz[x],sz[U.nxt[i]]);Msz[x]=max(Msz[x],ts-sz[x]);
if(!rt||Msz[x]<Msz[rt])rt=x;
}
void Dis(int x,int fa,int y,int w,int fr){
A[++O]=x;dep[x]=y;Fr[x]=fr;Dep[x]=w;
for(int i=U.num[x];i;i=U.last[i])if(U.nxt[i]!=fa&&!Vis[U.nxt[i]])Dis(U.nxt[i],x,y+U.w[i],w+1,fr);
}
void Cal(int x){
O=0;A[++O]=x;dep[x]=0;Fr[x]=x;Dep[x]=0;
for(int i=U.num[x];i;i=U.last[i])if(!Vis[U.nxt[i]])Dis(U.nxt[i],x,U.w[i],1,U.nxt[i]);sort(A+1,A+O+1,cmp);
H=0;B[++H]=A[1];for(int i=2;i<=O;i++)if(dep[A[i]]!=dep[A[i-1]]||Fr[A[i]]!=Fr[A[i-1]])B[++H]=A[i];
// for(int i=1;i<=H;i++)printf("%d ",dep[B[i]]);printf(":%d\n",x);//printf("%d %d\n",l,r),
// for(int i=1;i<=H;i++)printf("%d ",Fr[B[i]]);printf(":%d\n",x);
// for(int i=1;i<=H;i++)printf("%d ",Dep[B[i]]);printf(":%d\n",x);
// for(int i=1;i<=O;i++)printf("%3d ",dep[A[i]]);printf("|%d\n",x);//
// for(int i=1;i<=O;i++)printf("%3d ",Fr[A[i]]);printf("|%d\n",x);
// for(int i=1;i<=O;i++)printf("%3d ",Dep[A[i]]);printf("|%d\n",x);
for(int i=1;i<=Q;i++){
int l=1,r=H;
while(l<r)dep[B[l]]+dep[B[r]]>Qr[i]?r--:dep[B[l]]+dep[B[r]]<Qr[i]?l++:(Fr[B[l]]!=Fr[B[r]]?Ans=min(Ans,Dep[B[l]]+Dep[B[r]]):0,dep[B[r]]==dep[B[r-1]]?r--:l++);
// l=1,r=O;
// while(l<r)dep[A[l]]+dep[A[r]]>Qr[i]?r--:dep[A[l]]+dep[A[r]]<Qr[i]?l++:(Fr[A[l]]!=Fr[A[r]]?Ans=min(Ans,Dep[A[l]]+Dep[A[r]]):0,dep[A[l]]==dep[A[l+1]]?l++:r--);
}
// for(int i=1;i<=Q;i++){
// int l=1,r=H,z,cl,cr;
// while(l<r){
// z=0;dep[B[l]]+dep[B[r]]>Qr[i]?r--:dep[B[l]]+dep[B[r]]<Qr[i]?l++:z=1;
// if(z){
// cl=l;cr=r;if(dep[B[l]]==dep[B[r]]){for(int i=l;i<=min(l+3,r);i++)for(int j=i+1;j<=min(l+3,r);j++)if(Fr[B[i]]!=Fr[B[j]])Ans=min(Ans,Dep[B[i]]+Dep[B[j]]);l=r;continue;}
// while(dep[B[cr]]==dep[B[cr-1]]&&l<cr)cr--;while(dep[B[cl]]==dep[B[cl+1]]&&cl<r)cl++;for(int i=l;i<=min(l+3,cl);i++)for(int j=cr;j<=min(cr+3,r);j++)if(Fr[B[i]]!=Fr[B[j]])Ans=min(Ans,Dep[B[i]]+Dep[B[j]]);l=cl+1;r=cr-1;
// }
// }
// // l=1,r=O;
// // while(l<r)dep[A[l]]+dep[A[r]]>Qr[i]?r--:dep[A[l]]+dep[A[r]]<Qr[i]?l++:(Fr[A[l]]!=Fr[A[r]]?Ans=min(Ans,Dep[A[l]]+Dep[A[r]]):0,dep[A[l]]==dep[A[l+1]]?l++:r--);
// }
}
void Sol(int x){
Vis[x]=true;Cal(x);
for(int i=U.num[x];i;i=U.last[i])if(!Vis[U.nxt[i]])rt=0,Get_root(U.nxt[i],0,sz[U.nxt[i]]),Sol(rt);
}
int main(){
scanf("%d %d",&n,&Qr[1]);Msz[0]=n;Q=1;Ans=n;
for(int i=1;i<n;i++)scanf("%d %d %d",&p,&q,&v),p++,q++,Add_Edge(p,q,v),Add_Edge(q,p,v);
Get_root(1,0,n);Sol(rt);
// for(int i=1;i<=Q;i++)printf("%d\n",Ans[i]);
printf("%d",Ans==n?-1:Ans);
}