#include "race.h"
#include <vector>
#include <map>
#include <stdint.h>
static const int INF=1e9+7;
static std::vector<std::pair<int,int> > adj[200005];
static int ans=INF;
static int size[200005];
static int KK;
static bool dead[200005];
static int dfs_size(int node,int parent){
size[node]=1;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_size(child,node);
size[node]+=size[child];
}
}
static int find_centroid(int node,int parent,int total_size){
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
if(size[child]*2>total_size){
return find_centroid(child,node,total_size);
}
}
return node;
}
static void dfs_add(int node,int parent,int64_t dist,int len,std::map<int64_t,int>& best){
if(best.count(dist)){
best[dist]=std::min(best[dist],len);
}else{
best[dist]=len;
}
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_add(child,node,e.second,len+1,best);
}
}
static void dfs_test(int node,int parent,int64_t dist,int len,std::map<int64_t,int>& best){
if(best.count(KK-dist)){
ans=std::min(ans,best[KK-dist]+len);
}
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_test(child,node,e.second,len+1,best);
}
}
static void solve(int node){
dfs_size(node,node);
node=find_centroid(node,node,size[node]);
std::map<int64_t,int> best;
best[0]=0;
for(auto e:adj[node]){
int child=e.first;
dfs_test(child,node,e.second,1,best);
dfs_add(child,node,e.second,1,best);
}
dead[node]=true;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]) continue;
solve(child);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N;i++){
adj[i].clear();
}
ans=INF;
std::fill(dead,dead+N,false);
KK=K;
for(int i=0;i<N-1;i++){
adj[H[i][0]].emplace_back(H[i][1],L[i]);
adj[H[i][1]].emplace_back(H[i][0],L[i]);
}
solve(0);
return ans<INF?ans:-1;
}
Compilation message
race.cpp: In function 'int dfs_size(int, int)':
race.cpp:22:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |