| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 543161 | __Variatto | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e5+10, MAXV=1e6+10;
vector<pair<int,int>>g[MAX];
int n, k, centr, podd[MAX], o[MAX];
int odw[MAX], wynik=MAXV, mini[MAX];
void dfs(int v, int oj, int roz){
podd[v]=1, o[v]=oj;
int maxi=0;
for(auto s:g[v]){
if(s.fi!=oj && !odw[s.fi]){
dfs(s.fi, v, roz);
maxi=max(maxi, podd[s.fi]);
podd[v]+=podd[s.fi];
}
}
if(maxi<=roz/2 && (roz-podd[v])<=roz/2)
centr=v;
}
void zlicz(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
//cout<<v<<" "<<st<<" "<<mini[k-akt]<<" "<<ile<<"\n";
wynik=min(wynik, mini[k-akt]+ile);
for(auto s:g[v]){
if(odw[s.fi]<=st) continue;
zlicz(s.fi, v, st, akt+s.se, ile+1);
}
}
void dodaj(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
mini[akt]=min(mini[akt], ile);
for(auto s:g[v]){
if(odw[s.fi]<=st) continue;
dodaj(s.fi, v, st, akt+s.se, ile+1);
}
}
void zeruj(int v, int oj, int st, int akt, int ile){
if(akt>k) return;
mini[akt]=MAXV;
for(auto s:g[v]){
if(odw[s.fi]<=st) continue;
zeruj(s.fi, v, st, akt+s.se, ile+1);
}
}
void rek(int aktc, int roz, int st){
odw[aktc]=st;
for(auto s:g[aktc]){
if(!odw[s.fi]){
int newR=podd[s.fi];
if(s.fi==o[aktc]) newR=roz-podd[aktc];
centr=0;
dfs(s.fi, s.fi, newR);
rek(centr, newR, st+1);
}
}
mini[0]=0;
for(auto s: g[aktc]){
zlicz(s.fi, s.fi, st, 0, 0);
dodaj(s.fi, s.fi, st, 0, 0);
}
for(auto s: g[aktc])
zeruj(s.fi, s.fi, st, 0, 0);
}
int best_path(int N, int K, int H[][2], int L[]){
n=N, k=K;
for(int i=0; i<n-1; i++)
g[H[i][0]].pb({H[i][1], L[i]}), g[H[i][1]].pb({H[i][0], L[i]});
for(int i=0; i<=k; i++)
mini[i]=MAXV;
dfs(0, 0, n);
rek(centr, n, 1);
if(wynik==MAXV) wynik=-1;
return wynik;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int N, K;
cin>>N>>K;
int H[N+10][2], L[N+10];
for(int i=0; i<N-1; i++)
cin>>H[i][0]>>H[i][1]>>L[i];
cout<<best_path(N, K, H, L)<<"\n";
}