#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 best[1000005];
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){
if(dist>KK) return;
best[dist]=std::min(best[dist],len);
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_add(child,node,dist+e.second,len+1);
}
}
static void dfs_test(int node,int parent,int64_t dist,int len){
if(dist>KK) return;
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,dist+e.second,len+1);
}
}
static void dfs_rem(int node,int parent,int64_t dist,int len){
if(dist>KK) return;
best[dist]=INF;
for(auto e:adj[node]){
int child=e.first;
if(dead[child]||child==parent) continue;
dfs_rem(child,node,dist+e.second,len+1);
}
}
static void solve(int node){
dfs_size(node,node);
node=find_centroid(node,node,size[node]);
best[0]=0;
for(auto e:adj[node]){
int child=e.first;
dfs_test(child,node,e.second,1);
dfs_add(child,node,e.second,1);
}
for(auto e:adj[node]){
int child=e.first;
dfs_rem(child,node,e.second,1);
}
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;
std::fill(best,best+100001,INF);
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:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5504 KB |
Output is correct |
2 |
Correct |
6 ms |
5504 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
8 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
6 ms |
5504 KB |
Output is correct |
7 |
Correct |
6 ms |
5376 KB |
Output is correct |
8 |
Correct |
6 ms |
5376 KB |
Output is correct |
9 |
Correct |
6 ms |
5504 KB |
Output is correct |
10 |
Correct |
6 ms |
5504 KB |
Output is correct |
11 |
Correct |
6 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5376 KB |
Output is correct |
13 |
Correct |
6 ms |
5504 KB |
Output is correct |
14 |
Correct |
6 ms |
5504 KB |
Output is correct |
15 |
Correct |
6 ms |
5476 KB |
Output is correct |
16 |
Correct |
6 ms |
5504 KB |
Output is correct |
17 |
Correct |
5 ms |
5376 KB |
Output is correct |
18 |
Correct |
6 ms |
5504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5504 KB |
Output is correct |
2 |
Correct |
6 ms |
5504 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
8 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
6 ms |
5504 KB |
Output is correct |
7 |
Correct |
6 ms |
5376 KB |
Output is correct |
8 |
Correct |
6 ms |
5376 KB |
Output is correct |
9 |
Correct |
6 ms |
5504 KB |
Output is correct |
10 |
Correct |
6 ms |
5504 KB |
Output is correct |
11 |
Correct |
6 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5376 KB |
Output is correct |
13 |
Correct |
6 ms |
5504 KB |
Output is correct |
14 |
Correct |
6 ms |
5504 KB |
Output is correct |
15 |
Correct |
6 ms |
5476 KB |
Output is correct |
16 |
Correct |
6 ms |
5504 KB |
Output is correct |
17 |
Correct |
5 ms |
5376 KB |
Output is correct |
18 |
Correct |
6 ms |
5504 KB |
Output is correct |
19 |
Correct |
5 ms |
5504 KB |
Output is correct |
20 |
Correct |
6 ms |
5376 KB |
Output is correct |
21 |
Correct |
7 ms |
5504 KB |
Output is correct |
22 |
Incorrect |
10 ms |
8164 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5504 KB |
Output is correct |
2 |
Correct |
6 ms |
5504 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
8 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
6 ms |
5504 KB |
Output is correct |
7 |
Correct |
6 ms |
5376 KB |
Output is correct |
8 |
Correct |
6 ms |
5376 KB |
Output is correct |
9 |
Correct |
6 ms |
5504 KB |
Output is correct |
10 |
Correct |
6 ms |
5504 KB |
Output is correct |
11 |
Correct |
6 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5376 KB |
Output is correct |
13 |
Correct |
6 ms |
5504 KB |
Output is correct |
14 |
Correct |
6 ms |
5504 KB |
Output is correct |
15 |
Correct |
6 ms |
5476 KB |
Output is correct |
16 |
Correct |
6 ms |
5504 KB |
Output is correct |
17 |
Correct |
5 ms |
5376 KB |
Output is correct |
18 |
Correct |
6 ms |
5504 KB |
Output is correct |
19 |
Correct |
249 ms |
10780 KB |
Output is correct |
20 |
Correct |
247 ms |
10776 KB |
Output is correct |
21 |
Correct |
283 ms |
10744 KB |
Output is correct |
22 |
Correct |
246 ms |
10896 KB |
Output is correct |
23 |
Correct |
102 ms |
11000 KB |
Output is correct |
24 |
Correct |
98 ms |
10872 KB |
Output is correct |
25 |
Correct |
223 ms |
13688 KB |
Output is correct |
26 |
Correct |
132 ms |
16608 KB |
Output is correct |
27 |
Correct |
673 ms |
16232 KB |
Output is correct |
28 |
Correct |
379 ms |
30556 KB |
Output is correct |
29 |
Correct |
409 ms |
29792 KB |
Output is correct |
30 |
Correct |
685 ms |
19196 KB |
Output is correct |
31 |
Correct |
682 ms |
19276 KB |
Output is correct |
32 |
Correct |
823 ms |
19256 KB |
Output is correct |
33 |
Correct |
380 ms |
18040 KB |
Output is correct |
34 |
Correct |
294 ms |
18936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5504 KB |
Output is correct |
2 |
Correct |
6 ms |
5504 KB |
Output is correct |
3 |
Correct |
6 ms |
5376 KB |
Output is correct |
4 |
Correct |
8 ms |
5376 KB |
Output is correct |
5 |
Correct |
5 ms |
5376 KB |
Output is correct |
6 |
Correct |
6 ms |
5504 KB |
Output is correct |
7 |
Correct |
6 ms |
5376 KB |
Output is correct |
8 |
Correct |
6 ms |
5376 KB |
Output is correct |
9 |
Correct |
6 ms |
5504 KB |
Output is correct |
10 |
Correct |
6 ms |
5504 KB |
Output is correct |
11 |
Correct |
6 ms |
5504 KB |
Output is correct |
12 |
Correct |
6 ms |
5376 KB |
Output is correct |
13 |
Correct |
6 ms |
5504 KB |
Output is correct |
14 |
Correct |
6 ms |
5504 KB |
Output is correct |
15 |
Correct |
6 ms |
5476 KB |
Output is correct |
16 |
Correct |
6 ms |
5504 KB |
Output is correct |
17 |
Correct |
5 ms |
5376 KB |
Output is correct |
18 |
Correct |
6 ms |
5504 KB |
Output is correct |
19 |
Correct |
5 ms |
5504 KB |
Output is correct |
20 |
Correct |
6 ms |
5376 KB |
Output is correct |
21 |
Correct |
7 ms |
5504 KB |
Output is correct |
22 |
Incorrect |
10 ms |
8164 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |