#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = 1E18;
vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
if (N <= 2000) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
}
vector dp(N, vector(N, vector<ll>(2, inf)));
auto dfs = [&](auto dfs, int x, int p) -> void {
dp[x][0][0] = 0;
vector<pair<int, int>> ch;
for (auto [y, z] : adj[x]) {
if (y == p) {
continue;
}
dfs(dfs, y, x);
dp[x][0][0] += dp[y][0][0] + z;
ch.emplace_back(y, z);
}
for (int i = 1; i < N; i++) {
int cnt = ch.size();
ll sum = 0;
for (auto [y, z] : ch) {
sum += dp[y][i][1];
}
if (cnt <= i - 1) {
dp[x][i][1] = sum;
}
if (cnt <= i) {
dp[x][i][0] = sum;
}
vector<ll> v;
for (auto [y, z] : ch) {
v.push_back(z + dp[y][i][0] - dp[y][i][1]);
}
sort(v.begin(), v.end());
for (int j = 0; j < v.size(); j++) {
sum += v[j];
cnt--;
if (cnt <= i - 1) {
dp[x][i][1] = min(dp[x][i][1], sum);
}
if (cnt <= i) {
dp[x][i][0] = min(dp[x][i][0], sum);
}
}
}
};
dfs(dfs, 0, -1);
vector<ll> ans(N);
for (int i = 0; i < N; i++) {
ans[i] = dp[0][i][0];
}
return ans;
}
if (U == vector<int>(N - 1)) {
vector<ll> ans(N);
sort(W.begin(), W.end());
for (int i = 0; i < N - 1; i++) {
ans[N - i - 2] = ans[N - i - 1] + W[i];
}
return ans;
}
ll dp0 = 0, dp1 = 0;
for (int i = 0; i < N; i++) {
ll pd0 = dp0;
dp0 = max(dp0, dp1);
dp1 = W[i] + pd0;
}
vector<ll> ans(N);
ans[0] = accumulate(W.begin(), W.end(), 0LL);
ans[1] = ans[0] - max(dp0, dp1);
return ans;
}
Compilation message
roads.cpp: In lambda function:
roads.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
roads.cpp: In instantiation of 'minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)> [with auto:23 = minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23, int, int)>]':
roads.cpp:54:23: required from here
roads.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
548 ms |
194508 KB |
Output is correct |
3 |
Correct |
613 ms |
219852 KB |
Output is correct |
4 |
Correct |
483 ms |
219816 KB |
Output is correct |
5 |
Correct |
2 ms |
1236 KB |
Output is correct |
6 |
Correct |
5 ms |
2516 KB |
Output is correct |
7 |
Correct |
4 ms |
2516 KB |
Output is correct |
8 |
Correct |
357 ms |
156248 KB |
Output is correct |
9 |
Correct |
551 ms |
219856 KB |
Output is correct |
10 |
Correct |
4 ms |
2260 KB |
Output is correct |
11 |
Correct |
4 ms |
2528 KB |
Output is correct |
12 |
Correct |
23 ms |
2188 KB |
Output is correct |
13 |
Correct |
39 ms |
3392 KB |
Output is correct |
14 |
Correct |
46 ms |
3320 KB |
Output is correct |
15 |
Correct |
45 ms |
3644 KB |
Output is correct |
16 |
Correct |
47 ms |
3672 KB |
Output is correct |
17 |
Correct |
42 ms |
3796 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
37 ms |
3068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
30 ms |
2828 KB |
Output is correct |
3 |
Correct |
33 ms |
3212 KB |
Output is correct |
4 |
Correct |
36 ms |
3392 KB |
Output is correct |
5 |
Correct |
35 ms |
3388 KB |
Output is correct |
6 |
Correct |
305 ms |
165220 KB |
Output is correct |
7 |
Correct |
398 ms |
220108 KB |
Output is correct |
8 |
Correct |
307 ms |
178668 KB |
Output is correct |
9 |
Correct |
4 ms |
1876 KB |
Output is correct |
10 |
Correct |
6 ms |
2260 KB |
Output is correct |
11 |
Correct |
4 ms |
2516 KB |
Output is correct |
12 |
Correct |
28 ms |
2112 KB |
Output is correct |
13 |
Correct |
31 ms |
3404 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
37 ms |
3056 KB |
Output is correct |
16 |
Correct |
32 ms |
3396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
1492 KB |
Output is correct |
5 |
Correct |
5 ms |
2516 KB |
Output is correct |
6 |
Correct |
4 ms |
2216 KB |
Output is correct |
7 |
Correct |
5 ms |
2132 KB |
Output is correct |
8 |
Correct |
5 ms |
2516 KB |
Output is correct |
9 |
Correct |
5 ms |
2516 KB |
Output is correct |
10 |
Correct |
4 ms |
1876 KB |
Output is correct |
11 |
Correct |
4 ms |
2260 KB |
Output is correct |
12 |
Correct |
4 ms |
2516 KB |
Output is correct |
13 |
Correct |
2 ms |
1236 KB |
Output is correct |
14 |
Correct |
5 ms |
2476 KB |
Output is correct |
15 |
Correct |
4 ms |
2516 KB |
Output is correct |
16 |
Correct |
1 ms |
852 KB |
Output is correct |
17 |
Correct |
5 ms |
2516 KB |
Output is correct |
18 |
Correct |
4 ms |
2516 KB |
Output is correct |
19 |
Correct |
4 ms |
2260 KB |
Output is correct |
20 |
Correct |
4 ms |
2476 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
3 ms |
1492 KB |
Output is correct |
5 |
Correct |
5 ms |
2516 KB |
Output is correct |
6 |
Correct |
4 ms |
2216 KB |
Output is correct |
7 |
Correct |
5 ms |
2132 KB |
Output is correct |
8 |
Correct |
5 ms |
2516 KB |
Output is correct |
9 |
Correct |
5 ms |
2516 KB |
Output is correct |
10 |
Correct |
4 ms |
1876 KB |
Output is correct |
11 |
Correct |
4 ms |
2260 KB |
Output is correct |
12 |
Correct |
4 ms |
2516 KB |
Output is correct |
13 |
Correct |
2 ms |
1236 KB |
Output is correct |
14 |
Correct |
5 ms |
2476 KB |
Output is correct |
15 |
Correct |
4 ms |
2516 KB |
Output is correct |
16 |
Correct |
1 ms |
852 KB |
Output is correct |
17 |
Correct |
5 ms |
2516 KB |
Output is correct |
18 |
Correct |
4 ms |
2516 KB |
Output is correct |
19 |
Correct |
4 ms |
2260 KB |
Output is correct |
20 |
Correct |
4 ms |
2476 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
183 ms |
82744 KB |
Output is correct |
24 |
Correct |
401 ms |
219948 KB |
Output is correct |
25 |
Correct |
296 ms |
160400 KB |
Output is correct |
26 |
Correct |
372 ms |
219840 KB |
Output is correct |
27 |
Correct |
378 ms |
219872 KB |
Output is correct |
28 |
Correct |
364 ms |
219204 KB |
Output is correct |
29 |
Correct |
323 ms |
185908 KB |
Output is correct |
30 |
Correct |
372 ms |
219916 KB |
Output is correct |
31 |
Correct |
374 ms |
219864 KB |
Output is correct |
32 |
Correct |
416 ms |
219856 KB |
Output is correct |
33 |
Correct |
308 ms |
165264 KB |
Output is correct |
34 |
Correct |
398 ms |
220360 KB |
Output is correct |
35 |
Correct |
338 ms |
178736 KB |
Output is correct |
36 |
Correct |
517 ms |
194504 KB |
Output is correct |
37 |
Correct |
583 ms |
219856 KB |
Output is correct |
38 |
Correct |
492 ms |
219848 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
41 |
Correct |
3 ms |
1492 KB |
Output is correct |
42 |
Correct |
4 ms |
2516 KB |
Output is correct |
43 |
Correct |
4 ms |
2224 KB |
Output is correct |
44 |
Correct |
4 ms |
2004 KB |
Output is correct |
45 |
Correct |
5 ms |
2532 KB |
Output is correct |
46 |
Correct |
5 ms |
2492 KB |
Output is correct |
47 |
Correct |
3 ms |
1876 KB |
Output is correct |
48 |
Correct |
4 ms |
2364 KB |
Output is correct |
49 |
Correct |
5 ms |
2516 KB |
Output is correct |
50 |
Correct |
2 ms |
1236 KB |
Output is correct |
51 |
Correct |
5 ms |
2516 KB |
Output is correct |
52 |
Correct |
4 ms |
2476 KB |
Output is correct |
53 |
Correct |
242 ms |
131676 KB |
Output is correct |
54 |
Correct |
398 ms |
219884 KB |
Output is correct |
55 |
Correct |
383 ms |
219852 KB |
Output is correct |
56 |
Correct |
347 ms |
156160 KB |
Output is correct |
57 |
Correct |
564 ms |
219832 KB |
Output is correct |
58 |
Correct |
2 ms |
852 KB |
Output is correct |
59 |
Correct |
5 ms |
2516 KB |
Output is correct |
60 |
Correct |
5 ms |
2644 KB |
Output is correct |
61 |
Correct |
3 ms |
2224 KB |
Output is correct |
62 |
Correct |
5 ms |
2516 KB |
Output is correct |
63 |
Correct |
1 ms |
212 KB |
Output is correct |
64 |
Correct |
383 ms |
213312 KB |
Output is correct |
65 |
Correct |
388 ms |
219848 KB |
Output is correct |
66 |
Correct |
345 ms |
219800 KB |
Output is correct |
67 |
Correct |
429 ms |
219840 KB |
Output is correct |
68 |
Correct |
341 ms |
219764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
38 ms |
3232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
38 ms |
3232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
548 ms |
194508 KB |
Output is correct |
3 |
Correct |
613 ms |
219852 KB |
Output is correct |
4 |
Correct |
483 ms |
219816 KB |
Output is correct |
5 |
Correct |
2 ms |
1236 KB |
Output is correct |
6 |
Correct |
5 ms |
2516 KB |
Output is correct |
7 |
Correct |
4 ms |
2516 KB |
Output is correct |
8 |
Correct |
357 ms |
156248 KB |
Output is correct |
9 |
Correct |
551 ms |
219856 KB |
Output is correct |
10 |
Correct |
4 ms |
2260 KB |
Output is correct |
11 |
Correct |
4 ms |
2528 KB |
Output is correct |
12 |
Correct |
23 ms |
2188 KB |
Output is correct |
13 |
Correct |
39 ms |
3392 KB |
Output is correct |
14 |
Correct |
46 ms |
3320 KB |
Output is correct |
15 |
Correct |
45 ms |
3644 KB |
Output is correct |
16 |
Correct |
47 ms |
3672 KB |
Output is correct |
17 |
Correct |
42 ms |
3796 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
37 ms |
3068 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
30 ms |
2828 KB |
Output is correct |
22 |
Correct |
33 ms |
3212 KB |
Output is correct |
23 |
Correct |
36 ms |
3392 KB |
Output is correct |
24 |
Correct |
35 ms |
3388 KB |
Output is correct |
25 |
Correct |
305 ms |
165220 KB |
Output is correct |
26 |
Correct |
398 ms |
220108 KB |
Output is correct |
27 |
Correct |
307 ms |
178668 KB |
Output is correct |
28 |
Correct |
4 ms |
1876 KB |
Output is correct |
29 |
Correct |
6 ms |
2260 KB |
Output is correct |
30 |
Correct |
4 ms |
2516 KB |
Output is correct |
31 |
Correct |
28 ms |
2112 KB |
Output is correct |
32 |
Correct |
31 ms |
3404 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
37 ms |
3056 KB |
Output is correct |
35 |
Correct |
32 ms |
3396 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
3 ms |
1492 KB |
Output is correct |
40 |
Correct |
5 ms |
2516 KB |
Output is correct |
41 |
Correct |
4 ms |
2216 KB |
Output is correct |
42 |
Correct |
5 ms |
2132 KB |
Output is correct |
43 |
Correct |
5 ms |
2516 KB |
Output is correct |
44 |
Correct |
5 ms |
2516 KB |
Output is correct |
45 |
Correct |
4 ms |
1876 KB |
Output is correct |
46 |
Correct |
4 ms |
2260 KB |
Output is correct |
47 |
Correct |
4 ms |
2516 KB |
Output is correct |
48 |
Correct |
2 ms |
1236 KB |
Output is correct |
49 |
Correct |
5 ms |
2476 KB |
Output is correct |
50 |
Correct |
4 ms |
2516 KB |
Output is correct |
51 |
Correct |
1 ms |
852 KB |
Output is correct |
52 |
Correct |
5 ms |
2516 KB |
Output is correct |
53 |
Correct |
4 ms |
2516 KB |
Output is correct |
54 |
Correct |
4 ms |
2260 KB |
Output is correct |
55 |
Correct |
4 ms |
2476 KB |
Output is correct |
56 |
Correct |
1 ms |
212 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
183 ms |
82744 KB |
Output is correct |
59 |
Correct |
401 ms |
219948 KB |
Output is correct |
60 |
Correct |
296 ms |
160400 KB |
Output is correct |
61 |
Correct |
372 ms |
219840 KB |
Output is correct |
62 |
Correct |
378 ms |
219872 KB |
Output is correct |
63 |
Correct |
364 ms |
219204 KB |
Output is correct |
64 |
Correct |
323 ms |
185908 KB |
Output is correct |
65 |
Correct |
372 ms |
219916 KB |
Output is correct |
66 |
Correct |
374 ms |
219864 KB |
Output is correct |
67 |
Correct |
416 ms |
219856 KB |
Output is correct |
68 |
Correct |
308 ms |
165264 KB |
Output is correct |
69 |
Correct |
398 ms |
220360 KB |
Output is correct |
70 |
Correct |
338 ms |
178736 KB |
Output is correct |
71 |
Correct |
517 ms |
194504 KB |
Output is correct |
72 |
Correct |
583 ms |
219856 KB |
Output is correct |
73 |
Correct |
492 ms |
219848 KB |
Output is correct |
74 |
Correct |
1 ms |
212 KB |
Output is correct |
75 |
Correct |
1 ms |
212 KB |
Output is correct |
76 |
Correct |
3 ms |
1492 KB |
Output is correct |
77 |
Correct |
4 ms |
2516 KB |
Output is correct |
78 |
Correct |
4 ms |
2224 KB |
Output is correct |
79 |
Correct |
4 ms |
2004 KB |
Output is correct |
80 |
Correct |
5 ms |
2532 KB |
Output is correct |
81 |
Correct |
5 ms |
2492 KB |
Output is correct |
82 |
Correct |
3 ms |
1876 KB |
Output is correct |
83 |
Correct |
4 ms |
2364 KB |
Output is correct |
84 |
Correct |
5 ms |
2516 KB |
Output is correct |
85 |
Correct |
2 ms |
1236 KB |
Output is correct |
86 |
Correct |
5 ms |
2516 KB |
Output is correct |
87 |
Correct |
4 ms |
2476 KB |
Output is correct |
88 |
Correct |
242 ms |
131676 KB |
Output is correct |
89 |
Correct |
398 ms |
219884 KB |
Output is correct |
90 |
Correct |
383 ms |
219852 KB |
Output is correct |
91 |
Correct |
347 ms |
156160 KB |
Output is correct |
92 |
Correct |
564 ms |
219832 KB |
Output is correct |
93 |
Correct |
2 ms |
852 KB |
Output is correct |
94 |
Correct |
5 ms |
2516 KB |
Output is correct |
95 |
Correct |
5 ms |
2644 KB |
Output is correct |
96 |
Correct |
3 ms |
2224 KB |
Output is correct |
97 |
Correct |
5 ms |
2516 KB |
Output is correct |
98 |
Correct |
1 ms |
212 KB |
Output is correct |
99 |
Correct |
383 ms |
213312 KB |
Output is correct |
100 |
Correct |
388 ms |
219848 KB |
Output is correct |
101 |
Correct |
345 ms |
219800 KB |
Output is correct |
102 |
Correct |
429 ms |
219840 KB |
Output is correct |
103 |
Correct |
341 ms |
219764 KB |
Output is correct |
104 |
Incorrect |
38 ms |
3232 KB |
Output isn't correct |
105 |
Halted |
0 ms |
0 KB |
- |