| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 495699 | amsminn | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
N=f();K=f();
for(int i=1;i<=N-1;i++){
int p=f(),q=f(),r=f();++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;
}