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>
using namespace std;
#define ll long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ff first
#define ss second
#define pii pair<ll,ll>
#define pb push_back
vector<vector<pii>> graph;
vector<ll> sz,dist,rep,depth;
vector<bool> removed;
ll n,k,final;
void subtreesize(ll u, ll p){
sz[u]=1;
for(pii v:graph[u]){
if(v.ff==p) continue;
subtreesize(v.ff,u);
sz[u]+=sz[v.ff];
}
}
ll findcentroid(ll u, ll p, ll m){
for(pii v:graph[u]){
if(removed[v.ff]) continue;
if(v.ff==p) continue;
if(2*sz[v.ff]>m){
return findcentroid(v.ff,u,m);
}
}
return u;
}
void dfs(ll u, ll p, ll cen){
for(pii x:graph[u]){
ll v=x.ff,w=x.ss;
if(v==p) continue;
if(removed[v]) continue;
if(u!=cen) rep[v]=rep[u];
depth[v]=depth[u]+1;
dist[v]=dist[u]+w;
dfs(v,u,cen);
}
}
void centroid_decomp(ll u, ll p){
ll ctrd=findcentroid(u,p,sz[u]);
//cout<<"hi "<<u<<' '<<p<<' '<<ctrd<<'\n';
dist.clear();
dist.resize(n,0);
rep.clear();
rep.resize(n);
depth.clear();
depth.resize(n,0);
int random=0;
vector<int> bruh;
for(pii v:graph[ctrd]){
if(removed[v.ff]) continue;
rep[v.ff]=v.ff;
random++;
bruh.pb(v.ff);
}
dfs(ctrd,-1,ctrd);
ll ans=1e7;
map<int,int> hurb;
vector<vector<ll>> values(k+1,vector<ll>(random,1e7));
for(int i=0;i<random;i++){
values[0][i]=0;
hurb[bruh[i]]=i;
}
for(ll i=0;i<n;i++){
if(removed[i]) continue;
if(dist[i]==0 or depth[i]==0 or dist[i]>k) continue;
values[dist[i]][hurb[rep[i]]]=min(depth[i],values[dist[i]][hurb[rep[i]]]);
if(dist[i]>k) continue;
if(dist[i]==k){
ans=min(ans,depth[i]);
}
for(int j=0;j<random;j++){
if(bruh[j]==rep[i]) continue;
if(values[k-dist[i]][j]!=1e7){
ans=min(ans,values[k-dist[i]][j]+values[dist[i]][hurb[rep[i]]]);
}
}
}
final=min(final,ans);
removed[ctrd]=true;
for(pii v:graph[ctrd]){
if(removed[v.ff]) continue;
centroid_decomp(v.ff,ctrd);
}
}
int best_path(int N, int K, int h[][2], int l[]){
n=N,k=K;
graph.clear();
graph.resize(n);
sz.clear();
sz.resize(n);
removed.clear();
removed.resize(n);
dist.clear();
dist.resize(n);
for(ll i=0;i<n-1;i++){
graph[h[i][0]].pb({h[i][1],l[i]});
graph[h[i][1]].pb({h[i][0],l[i]});
}
final=1e7;
subtreesize(0,-1);
centroid_decomp(0,-1);
if(final==1e7){
return -1;
}else{
return final;
}
}
# | 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... |