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"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,fma,sse,sse2,sse4")
using namespace std;
typedef long long ll;
vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={0};
ll m[1000001];
ll k;
ll dfs_sizes(ll v, ll pV){
sz[v]=1;
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
sz[v]+=dfs_sizes(w,v);
}
}
return sz[v];
}
ll dfs_centroid(ll v, ll pV, ll subtree_sz){
for(auto [w,d] : adj[v]){
if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
return dfs_centroid(w,v,subtree_sz);
}
}
return v;
}
void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
a.push_back({dist,l});
for(auto [w,d] : adj[v]){
if(w!=pV&&!marked[w]){
if(dist+d<=k){
dfs_paths(w,v,dist+d,l+1,a);
}
}
}
}
ll centroid_decomposition(ll v){
ll c = dfs_centroid(v,v,dfs_sizes(v,v));
marked[c]=1;
ll ans=1000001;
vector<ll> sus;
m[0]=0;
for(auto [w,d] : adj[c]){
if(!marked[w]){
vector<pair<ll,ll>> a;
a.push_back({0,0});
dfs_paths(w,c,d,1,a);
for(auto [dist,l] : a){
if(m[k-dist]!=1000001){
ans=min(ans,l+m[k-dist]);
}
}
for(auto [dist,l] : a){
if(m[dist]!=1000001)m[dist]=min(m[dist],l);
else{
m[dist]=l;
sus.push_back(dist);
}
}
}
}
for(ll i : sus)m[i]=1000001;
m[0]=0;
for(auto [w,d] : adj[c]){
if(!marked[w]){
ans = min(ans,centroid_decomposition(w));
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
for(ll i=0;i<N-1;i++){
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
for(ll i=0;i<=k;i++)m[i]=1000001;
m[0]=0;
ll ans = centroid_decomposition(0);
return (ans==1000001?-1:ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |