#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define len(a) ((int)a.size())
const int N = 200005;
int ans = -1;
vector< pair<int, int> > g[N];
int sz[N], all, k;
bool used[N];
void update(int nans){
if(ans == -1 || nans < ans){
ans = nans;
}
}
void sizes(int v, int p){
sz[v] = 1;
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(to == p || used[to]) continue;
sizes(to, v);
sz[v] += sz[to];
}
}
int cfind(int v, int p){
if(p == -1){
all = sz[v];
}
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(to == p || used[to]) continue;
if(sz[to] > (all / 2)) {
return cfind(to, v);
}
}
return v;
}
vector< pair<int, int> > mas;
map<int, int> mp;
void solve(int v, int p, int d, int l){
if(p != -1){
mas.push_back(make_pair(d, l));
}
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first, len = g[v][i].second;
if(to == p || used[to]) continue;
solve(to, v, d + 1, l + len);
if(p == -1){
for(int j = 0; j < len(mas); j++){
int L = mas[j].second;
int D = mas[j].first;
if(L > k) continue;
if(L == k) {
update(D);
}
else if (mp.find(k - L) != mp.end()){
update(mp[k - L] + D);
}
}
for(int j = 0; j < len(mas); j++){
int dep = mas[j].first, dis = mas[j].second;
if(dis > k) continue;
if(mp.find(dis) != mp.end()){
mp[dis] = min(mp[dis], dep);
}
else {
mp[dis] = dep;
}
}
mas.clear();
}
}
}
void centroid_decomposition(){
queue<int> q;
q.push(1);
while(!q.empty()){
int v = q.front();
q.pop();
sizes(v, -1);
v = cfind(v, -1);
sizes(v, -1);
mp.clear();
solve(v, -1, 0, 0);
used[v] = true;
for(int i = 0; i < len(g[v]); i++){
int to = g[v][i].first;
if(used[to]) continue;
if(sz[to] == 1) continue;
q.push(to);
}
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N - 1; i++){
int u = H[i][0], v = H[i][1], d = L[i];
g[u].push_back(make_pair(v, d));
g[v].push_back(make_pair(u, d));
}
centroid_decomposition();
return ans;
}
//int main(){
// int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
// int H[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
//
// cout << best_path(11, 12, H, L) << endl;
// return 0;
//}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4932 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
5068 KB |
Output is correct |
23 |
Correct |
4 ms |
5028 KB |
Output is correct |
24 |
Correct |
4 ms |
5068 KB |
Output is correct |
25 |
Correct |
5 ms |
5068 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
5 ms |
5100 KB |
Output is correct |
29 |
Correct |
4 ms |
5068 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
4 ms |
5068 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
4 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
280 ms |
10792 KB |
Output is correct |
20 |
Correct |
279 ms |
10824 KB |
Output is correct |
21 |
Correct |
273 ms |
10820 KB |
Output is correct |
22 |
Correct |
254 ms |
10920 KB |
Output is correct |
23 |
Correct |
148 ms |
11072 KB |
Output is correct |
24 |
Correct |
86 ms |
10692 KB |
Output is correct |
25 |
Correct |
196 ms |
17388 KB |
Output is correct |
26 |
Correct |
131 ms |
18248 KB |
Output is correct |
27 |
Correct |
283 ms |
15924 KB |
Output is correct |
28 |
Correct |
567 ms |
30136 KB |
Output is correct |
29 |
Correct |
551 ms |
28144 KB |
Output is correct |
30 |
Correct |
294 ms |
15960 KB |
Output is correct |
31 |
Correct |
282 ms |
15920 KB |
Output is correct |
32 |
Correct |
434 ms |
15968 KB |
Output is correct |
33 |
Correct |
455 ms |
15676 KB |
Output is correct |
34 |
Correct |
390 ms |
15640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4972 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
4940 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
3 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4932 KB |
Output is correct |
21 |
Correct |
4 ms |
5068 KB |
Output is correct |
22 |
Correct |
4 ms |
5068 KB |
Output is correct |
23 |
Correct |
4 ms |
5028 KB |
Output is correct |
24 |
Correct |
4 ms |
5068 KB |
Output is correct |
25 |
Correct |
5 ms |
5068 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
4 ms |
5068 KB |
Output is correct |
28 |
Correct |
5 ms |
5100 KB |
Output is correct |
29 |
Correct |
4 ms |
5068 KB |
Output is correct |
30 |
Correct |
5 ms |
5068 KB |
Output is correct |
31 |
Correct |
5 ms |
5068 KB |
Output is correct |
32 |
Correct |
4 ms |
5068 KB |
Output is correct |
33 |
Correct |
4 ms |
5068 KB |
Output is correct |
34 |
Correct |
4 ms |
5068 KB |
Output is correct |
35 |
Correct |
4 ms |
5068 KB |
Output is correct |
36 |
Correct |
4 ms |
5068 KB |
Output is correct |
37 |
Correct |
4 ms |
5068 KB |
Output is correct |
38 |
Correct |
4 ms |
5068 KB |
Output is correct |
39 |
Correct |
280 ms |
10792 KB |
Output is correct |
40 |
Correct |
279 ms |
10824 KB |
Output is correct |
41 |
Correct |
273 ms |
10820 KB |
Output is correct |
42 |
Correct |
254 ms |
10920 KB |
Output is correct |
43 |
Correct |
148 ms |
11072 KB |
Output is correct |
44 |
Correct |
86 ms |
10692 KB |
Output is correct |
45 |
Correct |
196 ms |
17388 KB |
Output is correct |
46 |
Correct |
131 ms |
18248 KB |
Output is correct |
47 |
Correct |
283 ms |
15924 KB |
Output is correct |
48 |
Correct |
567 ms |
30136 KB |
Output is correct |
49 |
Correct |
551 ms |
28144 KB |
Output is correct |
50 |
Correct |
294 ms |
15960 KB |
Output is correct |
51 |
Correct |
282 ms |
15920 KB |
Output is correct |
52 |
Correct |
434 ms |
15968 KB |
Output is correct |
53 |
Correct |
455 ms |
15676 KB |
Output is correct |
54 |
Correct |
390 ms |
15640 KB |
Output is correct |
55 |
Correct |
22 ms |
5712 KB |
Output is correct |
56 |
Correct |
16 ms |
5636 KB |
Output is correct |
57 |
Correct |
159 ms |
11024 KB |
Output is correct |
58 |
Correct |
52 ms |
10420 KB |
Output is correct |
59 |
Correct |
307 ms |
21536 KB |
Output is correct |
60 |
Correct |
1095 ms |
36576 KB |
Output is correct |
61 |
Correct |
359 ms |
16264 KB |
Output is correct |
62 |
Correct |
355 ms |
16076 KB |
Output is correct |
63 |
Correct |
529 ms |
16252 KB |
Output is correct |
64 |
Correct |
1251 ms |
20932 KB |
Output is correct |
65 |
Correct |
528 ms |
16704 KB |
Output is correct |
66 |
Correct |
857 ms |
28884 KB |
Output is correct |
67 |
Correct |
125 ms |
16132 KB |
Output is correct |
68 |
Correct |
591 ms |
20428 KB |
Output is correct |
69 |
Correct |
539 ms |
20384 KB |
Output is correct |
70 |
Correct |
534 ms |
19736 KB |
Output is correct |