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>
typedef long long ll ;
using namespace std;
const int N = 200005;
vector < pair < int , int > > G[N];
int sub[N] , par[N];
bool blocked[N];
int n , k ;
void get_size(int u, int p){
par[u] = p ;
sub[u] = 1 ;
for(auto ch : G[u]){
int v = ch.first;
if(v == p || blocked[v]) continue ;
get_size(v , u);
sub[u] += sub[v];
}
}
set < pair < int , int > > se;
int dfs(int u , int p , ll w , int d){
if(w > k) return n ;
int ret = n ;
if(w == k) ret = d;
auto it = *se.lower_bound({k - w , 0});
if(it.first == k - w)
ret = min(ret , d + it.second) ;
for(auto ch : G[u]){
int v = ch.first , ww = ch.second ;
if(v == p || blocked[v]) continue ;
ret = min(ret , dfs(v , u , w + ww , d + 1));
}
return ret ;
}
void update(int u , int p , ll w , int d){
if(w > k) return ;
se.insert({w , d});
for(auto ch : G[u]){
int v = ch.first , ww = ch.second ;
if(v == p || blocked[v]) continue ;
update(v , u , w + ww , d + 1);
}
}
int solve(int u){
se.clear() ;
int ret = n ;
for(auto ch : G[u]){
int v = ch.first , w = ch.second ;
if(blocked[v]) continue ;
ret = min(ret , dfs(v , u , w , 1));
update(v , u , w , 1);
}
return ret;
}
int get_centroid(int src){
get_size(src , src);
queue < int > Q ;
Q.push(src);
int centroid = src , best = sub[src];
while(!Q.empty()){
int u = Q.front();
Q.pop();
int size = sub[src] - sub[u];
for(auto ch : G[u]){
int v = ch.first;
if(v == par[u] || blocked[v]) continue ;
Q.push(v);
size = max(size , sub[v]);
}
if(best > size){
best = size ;
centroid = u ;
}
}
blocked[centroid] = true ;
int ret = solve(centroid);
for(auto ch : G[centroid]){
int v = ch.first;
if(blocked[v]) continue ;
ret = min(ret , get_centroid(v));
}
return ret;
}
int best_path(int nn , int kk , int H[][2] , int L[]) {
n = nn ;
k = kk ;
vector < pair < int , int > > ve ;
for(int i = 0 ; i < n - 1 ; i++){
int u , v ;
u = H[i][0] , v = H[i][1] ;
ve.push_back({u , v});
}
for(int j = 0 ; j < n - 1 ; j++){
auto i = ve[j];
int x ; x = L[j];
G[i.first].push_back({i.second , x});
G[i.second].push_back({i.first , x});
}
int ans = get_centroid(0);
if(ans == n) ans = -1 ;
return 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... |