| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 543161 | __Variatto | 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>
#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";
}