| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1315919 | javkhlantogs | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
vector<vector<pll>> e;
vector<ll> sz;
vector<bool> rem;
map<ll,ll> cnt;
int ans=1e9,k;
ll getsz(ll u,ll p){
sz[u]=1;
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
sz[u]+=getsz(v.first,u);
}
return sz[u];
}
ll getct(ll u,ll p,ll n){
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
if(sz[v.first]>n/2) return getct(v.first,u,n);
}
return u;
}
void getans(ll u,ll p,ll d,ll l){
if(l>k) return;
if(cnt.find(k-l)!=cnt.end()) ans=min(ans,d+cnt[k-l]);
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
getans(v.first,u,d+1,l+v.second);
}
}
void update(ll u,ll p,ll d,ll l){
if(l>k) return;
if(cnt[l]>d or cnt[l]==0) cnt[l]=d;
for(auto v:e[u]){
if(v.first==p or rem[v.first]==1) continue;
update(v.first,u,d+1,l+v.second);
}
}
void decompose(ll u){
getsz(u,u);
ll ct=getct(u,u,sz[u]);
rem[ct]=1;
cnt.clear();
cnt[0]=0;
for(auto v:e[ct]){
if(rem[v.first]==1) continue;
getans(v.first,u,1,v.second);
update(v.first,u,1,v.second);
}
for(auto v:e[ct]){
if(rem[v.first]==1) continue;
decompose(v.first);
}
}
int best_path(int N,int K,int H[][2],int L[]){
ll n=N,k=K,i;
e.resize(n+1);
sz.resize(n+1);
rem.resize(n+1,1);
for(i=0; i<n-1; i++) {
e[H[i][0]].push_back({H[i][1],L[i]});
e[H[i][1]].push_back({H[i][0],L[i]});
}
decompose(1);
if(ans==1e9) return -1;
else return ans;
}