#pragma GCC optimize("O3,unroll-loops")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
const int LIM = 2e5+1,inf = 2e18;
vector<pii> edges[LIM];
vi sz(LIM),taken(LIM,0);
int szs(int node,int p) {
sz[node] = 1;
for (auto it : edges[node]) {
if (it.first == p || taken[it.first]) continue;
sz[node]+=szs(it.first,node);
}
return sz[node];
}
int cent(int node,int p,int x) {
for (auto it : edges[node]) {
if (taken[it.first] || it.first == p) continue;
if (sz[it.first]*2 > x) return cent(it.first,node,x);
}
return node;
}
vector<pii> v;
void dist(int node,int p, int dep,int sm) {
v.push_back({sm,dep});
for (auto it : edges[node]) if (it.first != p && !taken[it.first]) dist(it.first,node,dep+1,sm+it.second);
}
int ans = inf;
int mp[1000001];
int n,k;
void decompose(int node) {
int c = cent(node,node,szs(node,node));
taken[c] = 1;
mp[0] = 0;
vi seen;
for (auto it : edges[c]) {
if (taken[it.first]) continue;
dist(it.first,c,1,it.second);
for (auto itt : v) {
if (itt.first > k) continue;
ans = min(ans,itt.second+mp[k-itt.first]);
}
for (auto itt : v) {
if (itt.first > k) continue;
seen.push_back(itt.first);
mp[itt.first] = min(mp[itt.first],itt.second);
}
ans = min(ans,mp[k]);
v.clear();
}
for (auto it : seen) mp[it] = inf;
for (auto it : edges[c]) if (!taken[it.first]) decompose(it.first);
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[])
{
for (int i=0;i<=K;i++) mp[i] = inf;
n = N,k = K;
for (int i=0;i<n-1;i++) {
edges[H[i][0]+1].push_back({H[i][1]+1,L[i]});
edges[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
decompose(1);
return ans == inf?-1:ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13400 KB |
Output is correct |
2 |
Correct |
5 ms |
13404 KB |
Output is correct |
3 |
Correct |
4 ms |
13408 KB |
Output is correct |
4 |
Correct |
4 ms |
13404 KB |
Output is correct |
5 |
Correct |
4 ms |
13400 KB |
Output is correct |
6 |
Correct |
4 ms |
13600 KB |
Output is correct |
7 |
Correct |
5 ms |
13404 KB |
Output is correct |
8 |
Correct |
4 ms |
13404 KB |
Output is correct |
9 |
Correct |
4 ms |
13404 KB |
Output is correct |
10 |
Correct |
4 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13404 KB |
Output is correct |
12 |
Correct |
4 ms |
13600 KB |
Output is correct |
13 |
Correct |
4 ms |
13404 KB |
Output is correct |
14 |
Correct |
4 ms |
13404 KB |
Output is correct |
15 |
Correct |
4 ms |
13400 KB |
Output is correct |
16 |
Correct |
5 ms |
13420 KB |
Output is correct |
17 |
Correct |
4 ms |
13852 KB |
Output is correct |
18 |
Correct |
4 ms |
13420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13400 KB |
Output is correct |
2 |
Correct |
5 ms |
13404 KB |
Output is correct |
3 |
Correct |
4 ms |
13408 KB |
Output is correct |
4 |
Correct |
4 ms |
13404 KB |
Output is correct |
5 |
Correct |
4 ms |
13400 KB |
Output is correct |
6 |
Correct |
4 ms |
13600 KB |
Output is correct |
7 |
Correct |
5 ms |
13404 KB |
Output is correct |
8 |
Correct |
4 ms |
13404 KB |
Output is correct |
9 |
Correct |
4 ms |
13404 KB |
Output is correct |
10 |
Correct |
4 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13404 KB |
Output is correct |
12 |
Correct |
4 ms |
13600 KB |
Output is correct |
13 |
Correct |
4 ms |
13404 KB |
Output is correct |
14 |
Correct |
4 ms |
13404 KB |
Output is correct |
15 |
Correct |
4 ms |
13400 KB |
Output is correct |
16 |
Correct |
5 ms |
13420 KB |
Output is correct |
17 |
Correct |
4 ms |
13852 KB |
Output is correct |
18 |
Correct |
4 ms |
13420 KB |
Output is correct |
19 |
Correct |
4 ms |
13404 KB |
Output is correct |
20 |
Correct |
4 ms |
13404 KB |
Output is correct |
21 |
Correct |
5 ms |
13660 KB |
Output is correct |
22 |
Correct |
7 ms |
19800 KB |
Output is correct |
23 |
Correct |
6 ms |
19804 KB |
Output is correct |
24 |
Correct |
6 ms |
19800 KB |
Output is correct |
25 |
Correct |
6 ms |
19804 KB |
Output is correct |
26 |
Correct |
5 ms |
17768 KB |
Output is correct |
27 |
Correct |
5 ms |
19744 KB |
Output is correct |
28 |
Correct |
5 ms |
15708 KB |
Output is correct |
29 |
Correct |
5 ms |
17764 KB |
Output is correct |
30 |
Correct |
5 ms |
17756 KB |
Output is correct |
31 |
Correct |
5 ms |
19804 KB |
Output is correct |
32 |
Correct |
5 ms |
19800 KB |
Output is correct |
33 |
Correct |
6 ms |
20056 KB |
Output is correct |
34 |
Correct |
7 ms |
19640 KB |
Output is correct |
35 |
Correct |
7 ms |
19804 KB |
Output is correct |
36 |
Correct |
6 ms |
19800 KB |
Output is correct |
37 |
Correct |
5 ms |
19804 KB |
Output is correct |
38 |
Correct |
6 ms |
17756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13400 KB |
Output is correct |
2 |
Correct |
5 ms |
13404 KB |
Output is correct |
3 |
Correct |
4 ms |
13408 KB |
Output is correct |
4 |
Correct |
4 ms |
13404 KB |
Output is correct |
5 |
Correct |
4 ms |
13400 KB |
Output is correct |
6 |
Correct |
4 ms |
13600 KB |
Output is correct |
7 |
Correct |
5 ms |
13404 KB |
Output is correct |
8 |
Correct |
4 ms |
13404 KB |
Output is correct |
9 |
Correct |
4 ms |
13404 KB |
Output is correct |
10 |
Correct |
4 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13404 KB |
Output is correct |
12 |
Correct |
4 ms |
13600 KB |
Output is correct |
13 |
Correct |
4 ms |
13404 KB |
Output is correct |
14 |
Correct |
4 ms |
13404 KB |
Output is correct |
15 |
Correct |
4 ms |
13400 KB |
Output is correct |
16 |
Correct |
5 ms |
13420 KB |
Output is correct |
17 |
Correct |
4 ms |
13852 KB |
Output is correct |
18 |
Correct |
4 ms |
13420 KB |
Output is correct |
19 |
Correct |
100 ms |
22060 KB |
Output is correct |
20 |
Correct |
96 ms |
22940 KB |
Output is correct |
21 |
Correct |
87 ms |
22988 KB |
Output is correct |
22 |
Correct |
101 ms |
24332 KB |
Output is correct |
23 |
Correct |
86 ms |
23704 KB |
Output is correct |
24 |
Correct |
58 ms |
22228 KB |
Output is correct |
25 |
Correct |
96 ms |
28092 KB |
Output is correct |
26 |
Correct |
74 ms |
29004 KB |
Output is correct |
27 |
Correct |
145 ms |
28172 KB |
Output is correct |
28 |
Correct |
311 ms |
39364 KB |
Output is correct |
29 |
Correct |
283 ms |
39620 KB |
Output is correct |
30 |
Correct |
140 ms |
28620 KB |
Output is correct |
31 |
Correct |
128 ms |
28868 KB |
Output is correct |
32 |
Correct |
166 ms |
28588 KB |
Output is correct |
33 |
Correct |
210 ms |
29948 KB |
Output is correct |
34 |
Correct |
207 ms |
30084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
13400 KB |
Output is correct |
2 |
Correct |
5 ms |
13404 KB |
Output is correct |
3 |
Correct |
4 ms |
13408 KB |
Output is correct |
4 |
Correct |
4 ms |
13404 KB |
Output is correct |
5 |
Correct |
4 ms |
13400 KB |
Output is correct |
6 |
Correct |
4 ms |
13600 KB |
Output is correct |
7 |
Correct |
5 ms |
13404 KB |
Output is correct |
8 |
Correct |
4 ms |
13404 KB |
Output is correct |
9 |
Correct |
4 ms |
13404 KB |
Output is correct |
10 |
Correct |
4 ms |
13404 KB |
Output is correct |
11 |
Correct |
4 ms |
13404 KB |
Output is correct |
12 |
Correct |
4 ms |
13600 KB |
Output is correct |
13 |
Correct |
4 ms |
13404 KB |
Output is correct |
14 |
Correct |
4 ms |
13404 KB |
Output is correct |
15 |
Correct |
4 ms |
13400 KB |
Output is correct |
16 |
Correct |
5 ms |
13420 KB |
Output is correct |
17 |
Correct |
4 ms |
13852 KB |
Output is correct |
18 |
Correct |
4 ms |
13420 KB |
Output is correct |
19 |
Correct |
4 ms |
13404 KB |
Output is correct |
20 |
Correct |
4 ms |
13404 KB |
Output is correct |
21 |
Correct |
5 ms |
13660 KB |
Output is correct |
22 |
Correct |
7 ms |
19800 KB |
Output is correct |
23 |
Correct |
6 ms |
19804 KB |
Output is correct |
24 |
Correct |
6 ms |
19800 KB |
Output is correct |
25 |
Correct |
6 ms |
19804 KB |
Output is correct |
26 |
Correct |
5 ms |
17768 KB |
Output is correct |
27 |
Correct |
5 ms |
19744 KB |
Output is correct |
28 |
Correct |
5 ms |
15708 KB |
Output is correct |
29 |
Correct |
5 ms |
17764 KB |
Output is correct |
30 |
Correct |
5 ms |
17756 KB |
Output is correct |
31 |
Correct |
5 ms |
19804 KB |
Output is correct |
32 |
Correct |
5 ms |
19800 KB |
Output is correct |
33 |
Correct |
6 ms |
20056 KB |
Output is correct |
34 |
Correct |
7 ms |
19640 KB |
Output is correct |
35 |
Correct |
7 ms |
19804 KB |
Output is correct |
36 |
Correct |
6 ms |
19800 KB |
Output is correct |
37 |
Correct |
5 ms |
19804 KB |
Output is correct |
38 |
Correct |
6 ms |
17756 KB |
Output is correct |
39 |
Correct |
100 ms |
22060 KB |
Output is correct |
40 |
Correct |
96 ms |
22940 KB |
Output is correct |
41 |
Correct |
87 ms |
22988 KB |
Output is correct |
42 |
Correct |
101 ms |
24332 KB |
Output is correct |
43 |
Correct |
86 ms |
23704 KB |
Output is correct |
44 |
Correct |
58 ms |
22228 KB |
Output is correct |
45 |
Correct |
96 ms |
28092 KB |
Output is correct |
46 |
Correct |
74 ms |
29004 KB |
Output is correct |
47 |
Correct |
145 ms |
28172 KB |
Output is correct |
48 |
Correct |
311 ms |
39364 KB |
Output is correct |
49 |
Correct |
283 ms |
39620 KB |
Output is correct |
50 |
Correct |
140 ms |
28620 KB |
Output is correct |
51 |
Correct |
128 ms |
28868 KB |
Output is correct |
52 |
Correct |
166 ms |
28588 KB |
Output is correct |
53 |
Correct |
210 ms |
29948 KB |
Output is correct |
54 |
Correct |
207 ms |
30084 KB |
Output is correct |
55 |
Correct |
11 ms |
14428 KB |
Output is correct |
56 |
Correct |
10 ms |
14428 KB |
Output is correct |
57 |
Correct |
56 ms |
23536 KB |
Output is correct |
58 |
Correct |
36 ms |
23184 KB |
Output is correct |
59 |
Correct |
83 ms |
31308 KB |
Output is correct |
60 |
Correct |
318 ms |
49120 KB |
Output is correct |
61 |
Correct |
139 ms |
28644 KB |
Output is correct |
62 |
Correct |
150 ms |
36808 KB |
Output is correct |
63 |
Correct |
186 ms |
36928 KB |
Output is correct |
64 |
Correct |
341 ms |
35888 KB |
Output is correct |
65 |
Correct |
229 ms |
31416 KB |
Output is correct |
66 |
Correct |
278 ms |
44228 KB |
Output is correct |
67 |
Correct |
86 ms |
38156 KB |
Output is correct |
68 |
Correct |
192 ms |
38468 KB |
Output is correct |
69 |
Correct |
235 ms |
36072 KB |
Output is correct |
70 |
Correct |
160 ms |
38084 KB |
Output is correct |