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 "race.h"
#include <bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second
const int Ne = 2e5 + 5 ;
const int inf = 1e9 ;
template <class T>
bool chmax( T& x , const T& y ){
bool f = 0 ;
if ( x < y ) x = y , f = 1 ;
return f ;
}
template <class T>
bool chmin( T &x , const T &y ){
bool f = 0 ;
if ( x > y ) x = y , f = 1 ;
return f ;
}
int n , k , ans = inf , sz[Ne] ;
bool vis[Ne] ;
vector<vector<pair <int , int>>> mp ;
vector <pair <int , int>> g[Ne] ;
int fsz ( int v , int p = 0 ){
sz[v] = 1 ;
for ( auto to : g[v] ){
if ( to.ff != p && !vis[to.ff] ) fsz(to.ff,v) , sz[v] += sz[to.ff] ;
} return sz[v] ;
}
int centroid ( int v , int s , int p = 0 ){
for ( auto to : g[v] ){
if ( sz[to.ff] >= s && to.ff != p && !vis[to.ff] ) return centroid( to.ff , s , v ) ;
} return v ;
}
void dfs( int v , int d , int s , int p , int i ){
for ( auto j : mp[k-s] ) if ( j.ss != i ) chmin ( ans , j.ff+d ) ;
mp[s].push_back({d,i}) ;
for ( auto to : g[v] ){
if ( to.ff != p && !vis[to.ff] ) dfs( to.ff , d+1 , s+to.ss , v , i ) ;
}
}
void go ( int v ){
v = centroid( v , fsz(v)/2 ) ;
vis[v] = 1 ;
mp.clear() ;
mp.resize(k+2) ;
for ( auto to : g[v] ){
dfs ( to.ff , 1 , to.ss , 0 , to.ff ) ;
} for ( auto i : mp[k] ) chmin ( ans , i.ff ) ;
for ( auto to : g[v] ){
if ( !vis[to.ff] ) go (to.ff) ;
}
}
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]].push_back({h[i][1],l[i]}) ;
g[h[i][1]].push_back({h[i][0],l[i]}) ;
}
go(1) ;
return (ans == inf) ? -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... |