| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 412487 | 20160161simone | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}