#include <bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 2e5 + 7;
const int NN = 1e6 + 7;
const int mod = 1e9 + 7;
int n,k;
int ans = 1e9;
bool used[N];
int sz[N];
int m[NN];
vector < pair < int , int > > v[N];
void dfs( int x , int p , int d , vector < pair < int , int > > &t , int sum )
{
if( sum > k )return;
t.push_back({sum , d});
for( auto y : v[x] ){
if( y.fi != p && !used[y.fi] ){
dfs(y.fi , x , d + 1 , t , sum + y.se);
}
}
}
int centr( int x , int p , int n )
{
for( auto y : v[x] ){
if( y.fi != p && !used[y.fi] && sz[y.fi] > n / 2 ){
return centr(y.fi , x , n);
}
}
return x;
}
void siz( int x , int p )
{
sz[x] = 1;
for( auto y : v[x] ){
if( y.fi == p || used[y.fi] )continue;
siz(y.fi , x);
sz[x] += sz[y.fi];
}
}
vector < int > g;
vector < pair < int , int > > t;
void solve( int x )
{
siz(x , x);
g.clear();
for( auto y : v[x] ){
if(used[y.fi]) continue;
t.clear();
dfs(y.fi , x , 1 , t , y.se);
for( auto it : t ){
if( it.fi < k ){
if( m[k - it.fi] != mod ){
ans = min(ans , m[k - it.fi] + it.se);
}
}else if( it.fi == k ){
ans = min(ans , it.se);
}
}
for( auto it : t ){
if( it.fi >= k )continue;
m[it.fi] = min( m[it.fi] , it.se );
g.push_back(it.fi);
}
}
for( auto y : g ){
m[y] = mod;
}
used[x] = true;
for( auto y : v[x] ){
if( !used[y.fi] ){
solve(centr(y.fi , x , sz[y.fi]));
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for( int i = 0; i < n - 1; i++ ){
int x = H[i][0];
int y = H[i][1];
int z = L[i];
x++,y++;
v[x].push_back({y , z});
v[y].push_back({x , z});
}
for( int i = 0; i < NN; i++ ){
m[i] = mod;
}
siz(1 , 1);
solve(centr(1 , 1 , n));
if( ans == 1e9 )ans = -1;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
11 ms |
8952 KB |
Output is correct |
4 |
Correct |
9 ms |
8952 KB |
Output is correct |
5 |
Correct |
9 ms |
8956 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
9 ms |
8952 KB |
Output is correct |
12 |
Correct |
9 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8904 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
11 ms |
8952 KB |
Output is correct |
4 |
Correct |
9 ms |
8952 KB |
Output is correct |
5 |
Correct |
9 ms |
8956 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
9 ms |
8952 KB |
Output is correct |
12 |
Correct |
9 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8904 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8952 KB |
Output is correct |
19 |
Correct |
10 ms |
8992 KB |
Output is correct |
20 |
Correct |
10 ms |
8952 KB |
Output is correct |
21 |
Correct |
10 ms |
8952 KB |
Output is correct |
22 |
Correct |
10 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
8952 KB |
Output is correct |
24 |
Correct |
10 ms |
8952 KB |
Output is correct |
25 |
Correct |
10 ms |
9080 KB |
Output is correct |
26 |
Correct |
10 ms |
8952 KB |
Output is correct |
27 |
Correct |
10 ms |
8952 KB |
Output is correct |
28 |
Correct |
10 ms |
9084 KB |
Output is correct |
29 |
Correct |
11 ms |
9080 KB |
Output is correct |
30 |
Correct |
12 ms |
8952 KB |
Output is correct |
31 |
Correct |
13 ms |
8952 KB |
Output is correct |
32 |
Correct |
13 ms |
8952 KB |
Output is correct |
33 |
Correct |
11 ms |
8952 KB |
Output is correct |
34 |
Correct |
13 ms |
9080 KB |
Output is correct |
35 |
Correct |
12 ms |
8952 KB |
Output is correct |
36 |
Correct |
13 ms |
8952 KB |
Output is correct |
37 |
Correct |
12 ms |
8952 KB |
Output is correct |
38 |
Correct |
10 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
11 ms |
8952 KB |
Output is correct |
4 |
Correct |
9 ms |
8952 KB |
Output is correct |
5 |
Correct |
9 ms |
8956 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
9 ms |
8952 KB |
Output is correct |
12 |
Correct |
9 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8904 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8952 KB |
Output is correct |
19 |
Correct |
169 ms |
15864 KB |
Output is correct |
20 |
Correct |
151 ms |
15860 KB |
Output is correct |
21 |
Correct |
158 ms |
16120 KB |
Output is correct |
22 |
Correct |
157 ms |
16628 KB |
Output is correct |
23 |
Correct |
132 ms |
16120 KB |
Output is correct |
24 |
Correct |
88 ms |
15864 KB |
Output is correct |
25 |
Correct |
187 ms |
18552 KB |
Output is correct |
26 |
Correct |
131 ms |
22392 KB |
Output is correct |
27 |
Correct |
238 ms |
22904 KB |
Output is correct |
28 |
Correct |
390 ms |
34168 KB |
Output is correct |
29 |
Correct |
417 ms |
33160 KB |
Output is correct |
30 |
Correct |
225 ms |
22904 KB |
Output is correct |
31 |
Correct |
222 ms |
22812 KB |
Output is correct |
32 |
Correct |
281 ms |
23032 KB |
Output is correct |
33 |
Correct |
345 ms |
21672 KB |
Output is correct |
34 |
Correct |
334 ms |
22524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8952 KB |
Output is correct |
2 |
Correct |
10 ms |
8952 KB |
Output is correct |
3 |
Correct |
11 ms |
8952 KB |
Output is correct |
4 |
Correct |
9 ms |
8952 KB |
Output is correct |
5 |
Correct |
9 ms |
8956 KB |
Output is correct |
6 |
Correct |
10 ms |
8952 KB |
Output is correct |
7 |
Correct |
9 ms |
8952 KB |
Output is correct |
8 |
Correct |
10 ms |
8952 KB |
Output is correct |
9 |
Correct |
10 ms |
8952 KB |
Output is correct |
10 |
Correct |
9 ms |
8952 KB |
Output is correct |
11 |
Correct |
9 ms |
8952 KB |
Output is correct |
12 |
Correct |
9 ms |
8952 KB |
Output is correct |
13 |
Correct |
10 ms |
8952 KB |
Output is correct |
14 |
Correct |
9 ms |
8952 KB |
Output is correct |
15 |
Correct |
10 ms |
8904 KB |
Output is correct |
16 |
Correct |
10 ms |
8952 KB |
Output is correct |
17 |
Correct |
10 ms |
8952 KB |
Output is correct |
18 |
Correct |
9 ms |
8952 KB |
Output is correct |
19 |
Correct |
10 ms |
8992 KB |
Output is correct |
20 |
Correct |
10 ms |
8952 KB |
Output is correct |
21 |
Correct |
10 ms |
8952 KB |
Output is correct |
22 |
Correct |
10 ms |
8952 KB |
Output is correct |
23 |
Correct |
10 ms |
8952 KB |
Output is correct |
24 |
Correct |
10 ms |
8952 KB |
Output is correct |
25 |
Correct |
10 ms |
9080 KB |
Output is correct |
26 |
Correct |
10 ms |
8952 KB |
Output is correct |
27 |
Correct |
10 ms |
8952 KB |
Output is correct |
28 |
Correct |
10 ms |
9084 KB |
Output is correct |
29 |
Correct |
11 ms |
9080 KB |
Output is correct |
30 |
Correct |
12 ms |
8952 KB |
Output is correct |
31 |
Correct |
13 ms |
8952 KB |
Output is correct |
32 |
Correct |
13 ms |
8952 KB |
Output is correct |
33 |
Correct |
11 ms |
8952 KB |
Output is correct |
34 |
Correct |
13 ms |
9080 KB |
Output is correct |
35 |
Correct |
12 ms |
8952 KB |
Output is correct |
36 |
Correct |
13 ms |
8952 KB |
Output is correct |
37 |
Correct |
12 ms |
8952 KB |
Output is correct |
38 |
Correct |
10 ms |
8952 KB |
Output is correct |
39 |
Correct |
169 ms |
15864 KB |
Output is correct |
40 |
Correct |
151 ms |
15860 KB |
Output is correct |
41 |
Correct |
158 ms |
16120 KB |
Output is correct |
42 |
Correct |
157 ms |
16628 KB |
Output is correct |
43 |
Correct |
132 ms |
16120 KB |
Output is correct |
44 |
Correct |
88 ms |
15864 KB |
Output is correct |
45 |
Correct |
187 ms |
18552 KB |
Output is correct |
46 |
Correct |
131 ms |
22392 KB |
Output is correct |
47 |
Correct |
238 ms |
22904 KB |
Output is correct |
48 |
Correct |
390 ms |
34168 KB |
Output is correct |
49 |
Correct |
417 ms |
33160 KB |
Output is correct |
50 |
Correct |
225 ms |
22904 KB |
Output is correct |
51 |
Correct |
222 ms |
22812 KB |
Output is correct |
52 |
Correct |
281 ms |
23032 KB |
Output is correct |
53 |
Correct |
345 ms |
21672 KB |
Output is correct |
54 |
Correct |
334 ms |
22524 KB |
Output is correct |
55 |
Correct |
20 ms |
9720 KB |
Output is correct |
56 |
Correct |
20 ms |
9724 KB |
Output is correct |
57 |
Correct |
107 ms |
16756 KB |
Output is correct |
58 |
Correct |
52 ms |
16488 KB |
Output is correct |
59 |
Correct |
130 ms |
22388 KB |
Output is correct |
60 |
Correct |
591 ms |
35560 KB |
Output is correct |
61 |
Correct |
246 ms |
23164 KB |
Output is correct |
62 |
Correct |
256 ms |
23864 KB |
Output is correct |
63 |
Correct |
344 ms |
23772 KB |
Output is correct |
64 |
Correct |
549 ms |
25216 KB |
Output is correct |
65 |
Correct |
309 ms |
23728 KB |
Output is correct |
66 |
Correct |
531 ms |
31488 KB |
Output is correct |
67 |
Correct |
160 ms |
25192 KB |
Output is correct |
68 |
Correct |
337 ms |
24084 KB |
Output is correct |
69 |
Correct |
315 ms |
24336 KB |
Output is correct |
70 |
Correct |
308 ms |
23532 KB |
Output is correct |