#include "race.h"
#include<bits/stdc++.h>
using namespace std ;
const int NN = 1e6 + 7 ;
long long n , k ;
long long ans = 10000000000000 ;
vector<pair<long long , long long > > adj[NN] ;
long long hei[NN] , ldr[NN] , sz[NN];
long long fr[NN] , ls[NN] , ver[NN];
map<long long , map<long long , long long > > anss ;
int t = 1;
int dfz(int x , int p , long long h, int l = 1 ){
ver[t] = x ;
fr[x] = t++ ;
int ret = 1;
hei[x] = h ;
ldr[x] = l ;
for(auto u : adj[x]){
if(u.first==p)continue ;
ret+=dfz(u .first, x , h + u.second , l+1 ) ;
}
ls[x] = t++ ;
return sz[x] = ret ;
}
int dfs(int x , int p , bool keep){
int big = 0 ;
for(auto u : adj[x]){
if(u.first==p)continue ;
if(sz[u.first] > sz[big]){
big = u.first ;
}
}
for(auto u : adj[x]){
if(u.first ==p || u.first ==big)continue ;
dfs(u.first, x , 0) ;
}
if(big){
dfs(big , x , 1 ) ;
}
for(auto u : adj[x]){
if(u.first==p || u.first == big)continue ;
vector<int> v ;
for(int j = fr[u.first] ; j < ls[u.first] ;j ++ ){
if( ver[j] ){
long long he = hei[ver[j]] ;
long long dl = ldr[ver[j]] ;
long long drem = k - (hei[ver[j]] - hei[x] ) ;
v.push_back(j) ;
if( drem <=0)continue ;
for(auto u : anss[ hei[x] + drem ]){
if(u.second){
ans = min(ans , u.first - ldr[x] + dl - ldr[x]) ;
}
}
}
}
for(auto e : v){
anss[hei[ver[e]]][ ldr[ver[e]] ]++ ;
}
}
anss[hei[x]][ldr[x]]++;
for(auto u: anss[hei[x] + k] ){
if(u.second){
ans = min(ans , u.first - ldr[x] ) ;
}
}
if(!keep){
for(int i = fr[x] ; i < ls[x] ; i++){
anss[hei[ver[i]]][ldr[ver[i]]] -- ;
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N ;
k = K ;
bool zez = 0 ;
for(int i = 0 ;i < n-1 ;i++){
adj[H[i][0]+1].push_back({H[i][1]+1 , L[i]}) ;
adj[H[i][1]+1].push_back({H[i][0]+1, L[i]}) ;
zez|=!L[i] ;
}
dfz(1 , 1 , 0) ;
dfs(1 , 1 , 0) ;
if(ans==10000000000000) ans = -1 ;
if(!k&&zez)ans = 1 ;
return ans ;
}
Compilation message
race.cpp: In function 'int dfs(int, int, bool)':
race.cpp:49:27: warning: unused variable 'he' [-Wunused-variable]
long long he = hei[ver[j]] ;
^~
race.cpp:76:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
18 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
21 ms |
23936 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
21 ms |
23936 KB |
Output is correct |
9 |
Correct |
18 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
20 ms |
23968 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
21 ms |
23956 KB |
Output is correct |
14 |
Correct |
20 ms |
23896 KB |
Output is correct |
15 |
Correct |
21 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
22 ms |
23936 KB |
Output is correct |
18 |
Correct |
18 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
18 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
21 ms |
23936 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
21 ms |
23936 KB |
Output is correct |
9 |
Correct |
18 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
20 ms |
23968 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
21 ms |
23956 KB |
Output is correct |
14 |
Correct |
20 ms |
23896 KB |
Output is correct |
15 |
Correct |
21 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
22 ms |
23936 KB |
Output is correct |
18 |
Correct |
18 ms |
23936 KB |
Output is correct |
19 |
Correct |
23 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
24 ms |
24192 KB |
Output is correct |
22 |
Correct |
23 ms |
24320 KB |
Output is correct |
23 |
Correct |
20 ms |
24320 KB |
Output is correct |
24 |
Correct |
23 ms |
24320 KB |
Output is correct |
25 |
Correct |
20 ms |
24448 KB |
Output is correct |
26 |
Correct |
23 ms |
24320 KB |
Output is correct |
27 |
Correct |
19 ms |
23936 KB |
Output is correct |
28 |
Correct |
21 ms |
24448 KB |
Output is correct |
29 |
Correct |
25 ms |
24448 KB |
Output is correct |
30 |
Correct |
21 ms |
24448 KB |
Output is correct |
31 |
Correct |
20 ms |
24448 KB |
Output is correct |
32 |
Correct |
20 ms |
24448 KB |
Output is correct |
33 |
Correct |
21 ms |
24448 KB |
Output is correct |
34 |
Correct |
24 ms |
24320 KB |
Output is correct |
35 |
Correct |
22 ms |
24320 KB |
Output is correct |
36 |
Correct |
23 ms |
24320 KB |
Output is correct |
37 |
Correct |
20 ms |
24320 KB |
Output is correct |
38 |
Correct |
23 ms |
24320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
18 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
21 ms |
23936 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
21 ms |
23936 KB |
Output is correct |
9 |
Correct |
18 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
20 ms |
23968 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
21 ms |
23956 KB |
Output is correct |
14 |
Correct |
20 ms |
23896 KB |
Output is correct |
15 |
Correct |
21 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
22 ms |
23936 KB |
Output is correct |
18 |
Correct |
18 ms |
23936 KB |
Output is correct |
19 |
Correct |
312 ms |
36216 KB |
Output is correct |
20 |
Correct |
289 ms |
37424 KB |
Output is correct |
21 |
Correct |
317 ms |
37624 KB |
Output is correct |
22 |
Correct |
260 ms |
37384 KB |
Output is correct |
23 |
Correct |
368 ms |
38368 KB |
Output is correct |
24 |
Correct |
245 ms |
37240 KB |
Output is correct |
25 |
Correct |
183 ms |
51192 KB |
Output is correct |
26 |
Correct |
271 ms |
57848 KB |
Output is correct |
27 |
Correct |
364 ms |
54520 KB |
Output is correct |
28 |
Correct |
368 ms |
129404 KB |
Output is correct |
29 |
Correct |
374 ms |
126968 KB |
Output is correct |
30 |
Correct |
459 ms |
54520 KB |
Output is correct |
31 |
Correct |
478 ms |
54392 KB |
Output is correct |
32 |
Correct |
595 ms |
54904 KB |
Output is correct |
33 |
Correct |
402 ms |
51008 KB |
Output is correct |
34 |
Correct |
1307 ms |
100464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23936 KB |
Output is correct |
2 |
Correct |
18 ms |
23936 KB |
Output is correct |
3 |
Correct |
18 ms |
23936 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
21 ms |
23936 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
21 ms |
23936 KB |
Output is correct |
9 |
Correct |
18 ms |
23936 KB |
Output is correct |
10 |
Correct |
18 ms |
23936 KB |
Output is correct |
11 |
Correct |
20 ms |
23968 KB |
Output is correct |
12 |
Correct |
18 ms |
23936 KB |
Output is correct |
13 |
Correct |
21 ms |
23956 KB |
Output is correct |
14 |
Correct |
20 ms |
23896 KB |
Output is correct |
15 |
Correct |
21 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23936 KB |
Output is correct |
17 |
Correct |
22 ms |
23936 KB |
Output is correct |
18 |
Correct |
18 ms |
23936 KB |
Output is correct |
19 |
Correct |
23 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
24 ms |
24192 KB |
Output is correct |
22 |
Correct |
23 ms |
24320 KB |
Output is correct |
23 |
Correct |
20 ms |
24320 KB |
Output is correct |
24 |
Correct |
23 ms |
24320 KB |
Output is correct |
25 |
Correct |
20 ms |
24448 KB |
Output is correct |
26 |
Correct |
23 ms |
24320 KB |
Output is correct |
27 |
Correct |
19 ms |
23936 KB |
Output is correct |
28 |
Correct |
21 ms |
24448 KB |
Output is correct |
29 |
Correct |
25 ms |
24448 KB |
Output is correct |
30 |
Correct |
21 ms |
24448 KB |
Output is correct |
31 |
Correct |
20 ms |
24448 KB |
Output is correct |
32 |
Correct |
20 ms |
24448 KB |
Output is correct |
33 |
Correct |
21 ms |
24448 KB |
Output is correct |
34 |
Correct |
24 ms |
24320 KB |
Output is correct |
35 |
Correct |
22 ms |
24320 KB |
Output is correct |
36 |
Correct |
23 ms |
24320 KB |
Output is correct |
37 |
Correct |
20 ms |
24320 KB |
Output is correct |
38 |
Correct |
23 ms |
24320 KB |
Output is correct |
39 |
Correct |
312 ms |
36216 KB |
Output is correct |
40 |
Correct |
289 ms |
37424 KB |
Output is correct |
41 |
Correct |
317 ms |
37624 KB |
Output is correct |
42 |
Correct |
260 ms |
37384 KB |
Output is correct |
43 |
Correct |
368 ms |
38368 KB |
Output is correct |
44 |
Correct |
245 ms |
37240 KB |
Output is correct |
45 |
Correct |
183 ms |
51192 KB |
Output is correct |
46 |
Correct |
271 ms |
57848 KB |
Output is correct |
47 |
Correct |
364 ms |
54520 KB |
Output is correct |
48 |
Correct |
368 ms |
129404 KB |
Output is correct |
49 |
Correct |
374 ms |
126968 KB |
Output is correct |
50 |
Correct |
459 ms |
54520 KB |
Output is correct |
51 |
Correct |
478 ms |
54392 KB |
Output is correct |
52 |
Correct |
595 ms |
54904 KB |
Output is correct |
53 |
Correct |
402 ms |
51008 KB |
Output is correct |
54 |
Correct |
1307 ms |
100464 KB |
Output is correct |
55 |
Correct |
47 ms |
27000 KB |
Output is correct |
56 |
Correct |
32 ms |
25216 KB |
Output is correct |
57 |
Correct |
180 ms |
37748 KB |
Output is correct |
58 |
Correct |
93 ms |
36328 KB |
Output is correct |
59 |
Correct |
188 ms |
76280 KB |
Output is correct |
60 |
Correct |
438 ms |
127864 KB |
Output is correct |
61 |
Correct |
488 ms |
61688 KB |
Output is correct |
62 |
Correct |
363 ms |
55240 KB |
Output is correct |
63 |
Correct |
481 ms |
55312 KB |
Output is correct |
64 |
Correct |
2357 ms |
104632 KB |
Output is correct |
65 |
Correct |
1655 ms |
100744 KB |
Output is correct |
66 |
Correct |
515 ms |
122720 KB |
Output is correct |
67 |
Correct |
266 ms |
50524 KB |
Output is correct |
68 |
Correct |
1326 ms |
115960 KB |
Output is correct |
69 |
Correct |
1287 ms |
116752 KB |
Output is correct |
70 |
Correct |
1286 ms |
112504 KB |
Output is correct |