| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 478715 | Ronin13 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define epb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define inf 1e9+1
#define linf 1e18+1
using namespace std;
const int NMAX=1e6+1;
vector<vector<pii> >g(NMAX);
vector<int>d(NMAX,inf);
vector<int>t(NMAX);
vector<int>cmp;
vector<bool>used(NMAX);
void dfs(int v,int e=-1){
t[v]=1;
for(pii x:g[v]){
int to=x.f;
if(to==e)continue;
if(used[to])continue;
dfs(to,v);
t[v]+=t[to];
}
}
int n;
int cent(int v,int sz,int e=-1){
bool isc=true;
if(sz-t[v]>sz/2)isc=false;
for(pii x:g[v]){
int to=x.f;
if(to==e)continue;
if(used[to])continue;
if(t[to]>sz/2)isc=false;
}
if(isc)return v;
for(pii x:g[v]){
int to=x.f;
if(to==e)continue;
if(used[to])continue;
int an=cent(to,sz,v);
if(an!=-1)return an;
}
return -1;
}
int k;
int mn=inf;
void DFS(int v,int depth,int depthl,int e=-1){
if(depthl>k)return;
mn=min(mn,depth+d[k-depthl]);
for(pii x:g[v]){
int to=x.f,len=x.s;
if(to==e)continue;
if(used[to])continue;
if(depthl+len>k)continue;
DFS(to,depth+1,depthl+len,v);
}
}
void DFS2(int v,int depth,int depthl,int e=-1){
if(depthl>k)return;
d[depthl]=min(d[depthl],depth);
for(pii x:g[v]){
int to=x.f,len=x.s;
if(to==e)continue;
if(used[to])continue;
if(depthl+len>k)continue;
DFS2(to,depth+1,depthl+len,v);
}
}
void clear_dfs(int v,int depth,int depthl,int e=-1){
if(depthl>k)return;
//mn=min(mn,depth+d[k-depthl]);
for(pii x:g[v]){
int to=x.f,len=x.s;
if(to==e)continue;
if(used[to])continue;
if(depthl+len>k)continue;
clear_dfs(to,depth+1,depthl+len,v);
d[depthl+len]=inf;
}
}
void rec(int v){
dfs(v);
int sz=t[v];
int c=cent(v,sz);
if(c==-1)return;
d[0]=0;
for(pii x:g[c]){
int to=x.f;
if(used[to])continue;
DFS(to,1,x.s,c);
DFS2(to,1,x.s,c);
}
used[c]=true;
clear_dfs(c,0,0);
for(pii x:g[c]){
int to=x.f;
if(used[to])continue;
rec(to);
}
}
void solve(){
cin>>n;
cin>>k;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
int len;cin>>len;
g[u].pb({v,len});
g[v].pb({u,len});
}
rec(1);
if(mn==inf)cout<<-1;
else
cout<<mn<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
int test=1;//cin>>test;
while(test--){
solve();
}
}