| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 495702 | amsminn | 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 "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}
int N,K,ans=1e9;
int sz[202020];
int del[202020];
int mp[1010101];
vector<pi>v[202020];
vector<int>D;
int getsize(int x,int p=0){
sz[x]=1;
for(auto&[i,j]:v[x])if(i!=p and !del[i])sz[x]+=getsize(i,x);
return sz[x];
}
int getCent(int x,int p,int cap){
for(auto&[i,j]:v[x])if(i!=p and !del[i] and sz[i]*2>cap)
return getCent(i,x,cap);
return x;
}
void qry(int x,int p,int dist,int dep){
if(dist>K)return;
if(mp[K-dist]!=-1 and mp[K-dist]+dep<ans)ans=mp[K-dist]+dep;
for(auto&[i,j]:v[x])if(i!=p and !del[i])qry(i,x,dist+j,dep+1);
}
void upd(int x,int p,int dist,int dep){
if(dist>K)return;
D.pb(dist);
if(mp[dist]==-1)mp[dist]=dep;
else if(dep<mp[dist])mp[dist]=dep;
for(auto&[i,j]:v[x])if(i!=p and !del[i])upd(i,x,dist+j,dep+1);
}
void dnc(int x){
int cap=getsize(x,0);
int cent=getCent(x,0,cap);
del[x]=1;mp[0]=0;
for(auto&[i,j]:v[x])if(!del[i]){
qry(i,cent,j,1);
upd(i,cent,j,1);
}
for(auto&i:D)mp[i]=-1;D.clear();
for(auto&[i,j]:v[x])if(!del[i])dnc(i);
}
//#include <unistd.h>
//#include <sys/stat.h>
//#include <sys/mman.h>
//int z[36];
//char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
//inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>N>>K;
for(int i=1;i<=N-1;i++){
int p,q,r;cin>>p>>q>>r;++p;++q;
v[p].pb({q,r});
v[q].pb({p,r});
}
memset(mp,-1,sizeof mp);
dnc(1);
if(ans==1e9)cout<<-1<<endl;
else cout<<ans<<endl;
}