#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "roads.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2010;
int n;
long long f[N][N];
vector <long long> tmp[N];
vector <pair <int, int> > g[N];
void dfs(int u, int p) {
for (auto [v, w]: g[u])
if (v != p) dfs(v, u);
for (auto [v, w]: g[u]) {
if (v == p) continue;
for (int i = 0; i < n; ++i) f[u][i] += f[v][i] + w;
for (int i = 1; i < n; ++i)
tmp[i].push_back(- f[v][i - 1] + f[v][i] + w);
}
for (int i = 1; i < n; ++i) {
sort(tmp[i].begin(), tmp[i].end(), greater<>());
for (int j = 0; j < i && j < tmp[i].size() && tmp[i][j] > 0; ++j)
f[u][i] -= tmp[i][j];
tmp[i].clear();
}
// for (int i = 1; i < n; ++i) f[u][i] = max(f[u][i], f[u][i - 1]);
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
std::vector<int> V,
std::vector<int> W) {
n = N;
for (int i = 0; i < N - 1; ++i) {
int u = U[i], v = V[i], w = W[i];
++u, ++v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1, 0);
vector <long long> ans;
for (int i = 0; i < n; ++i) ans.push_back(f[1][i]);
return ans;
}
//
//int main() {
// int N;
// assert(1 == scanf("%d", &N));
//
// std::vector<int> U(N - 1), V(N - 1), W(N - 1);
// for (int i = 0; i < N - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
//
// std::vector<long long> closure_costs = minimum_closure_costs(N, U, V, W);
// for (int i = 0; i < static_cast<int>(closure_costs.size()); ++i) {
// if (i > 0) {
// printf(" ");
// }
// printf("%lld",closure_costs[i]);
// }
// printf("\n");
// return 0;
//}
Compilation message
roads.cpp: In function 'void dfs(int, int)':
roads.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for (auto [v, w]: g[u])
| ^
roads.cpp:24:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for (auto [v, w]: g[u]) {
| ^
roads.cpp:32:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int j = 0; j < i && j < tmp[i].size() && tmp[i][j] > 0; ++j)
| ~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
175 ms |
30904 KB |
Output is correct |
3 |
Correct |
221 ms |
32820 KB |
Output is correct |
4 |
Correct |
106 ms |
32752 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
99 ms |
27644 KB |
Output is correct |
9 |
Correct |
139 ms |
32780 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Runtime error |
114 ms |
10992 KB |
Execution killed with signal 11 |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Runtime error |
52 ms |
37344 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1654 ms |
16964 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1654 ms |
16964 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
175 ms |
30904 KB |
Output is correct |
3 |
Correct |
221 ms |
32820 KB |
Output is correct |
4 |
Correct |
106 ms |
32752 KB |
Output is correct |
5 |
Correct |
1 ms |
724 KB |
Output is correct |
6 |
Correct |
2 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
99 ms |
27644 KB |
Output is correct |
9 |
Correct |
139 ms |
32780 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
852 KB |
Output is correct |
12 |
Runtime error |
114 ms |
10992 KB |
Execution killed with signal 11 |
13 |
Halted |
0 ms |
0 KB |
- |