#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 = 3e5 + 10;
int n, k;
long long f[N][2];
set <pair <int, int> > g[N];
vector <int> s[N];
int vis[N], ti;
struct Set {
struct node {
int to[2];
int cnt;
long long sum;
};
int nNode = 0;
vector <node> T = {node()};
void add(long long x) {
int u = 0;
for (int i = 60; i >= 0; --i) {
if (!T[u].to[x >> i & 1]) T[u].to[x >> i & 1] = ++nNode, T.push_back(node());
u = T[u].to[x >> i & 1];
++T[u].cnt;
T[u].sum += x;
}
}
void rev(long long x) {
int u = 0;
for (int i = 60; i >= 0; --i) {
u = T[u].to[x >> i & 1];
--T[u].cnt;
T[u].sum -= x;
}
}
long long get(int k) {
int u = 0;
long long ans = 0;
for (int i = 60; i >= 0; --i) {
if (T[T[u].to[1]].cnt <= k) {
ans += T[T[u].to[1]].sum;
k -= T[T[u].to[1]].cnt;
u = T[u].to[0];
} else u = T[u].to[1];
if (u == 0) return ans;
}
return ans;
}
} S[N];
long long d[N];
inline void dfs(int u, int p) {
vis[u] = ti;
f[u][0] = f[u][1] = d[u];
for (auto [v, w]: g[u])
if (v != p) dfs(v, u);
vector <long long> tmp;
for (auto [v, w]: g[u]) {
if (v == p) continue;
f[u][0] += f[v][0] + w;
f[u][1] += f[v][0] + w;
if (- f[v][1] + f[v][0] + w > 0) S[u].add(- f[v][1] + f[v][0] + w), tmp.push_back(- f[v][1] + f[v][0] + w);
}
if (k) {
f[u][0] -= S[u].get(k);
f[u][1] -= S[u].get(k - 1);
}
for (auto x: tmp) S[u].rev(x);
}
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].insert({v, w});
g[v].insert({u, w});
}
for (int i = 1; i <= n; ++i) s[g[i].size()].push_back(i);
set <int> rem;
for (int i = 1; i <= n; ++i) rem.insert(i);
vector <long long> ans;
for (k = 0; k < n; ++k) {
++ti;
long long cost = 0;
for (auto u: s[k]) {
for (auto [v, w]: g[u]) {
d[v] += w;
g[v].erase({u, w});
S[v].add(w);
}
g[u].clear();
rem.erase(u);
}
for (auto u: rem) if (vis[u] != ti) dfs(u, 0), cost += f[u][0];
ans.push_back(cost);
}
return ans;
}
//
//int main() {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
// 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:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | for (auto [v, w]: g[u])
| ^
roads.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
70 | for (auto [v, w]: g[u]) {
| ^
roads.cpp: In function 'std::vector<long long int> minimum_closure_costs(int, std::vector<int>, std::vector<int>, std::vector<int>)':
roads.cpp:101:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | for (auto [v, w]: g[u]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
40148 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42188 KB |
Output is correct |
| 3 |
Correct |
37 ms |
42208 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
40584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
40148 KB |
Output is correct |
| 2 |
Correct |
515 ms |
316664 KB |
Output is correct |
| 3 |
Correct |
570 ms |
358732 KB |
Output is correct |
| 4 |
Correct |
586 ms |
375272 KB |
Output is correct |
| 5 |
Correct |
430 ms |
230512 KB |
Output is correct |
| 6 |
Correct |
44 ms |
46044 KB |
Output is correct |
| 7 |
Correct |
45 ms |
46852 KB |
Output is correct |
| 8 |
Incorrect |
40 ms |
43516 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
40148 KB |
Output is correct |
| 2 |
Correct |
27 ms |
40152 KB |
Output is correct |
| 3 |
Incorrect |
27 ms |
40276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
40148 KB |
Output is correct |
| 2 |
Correct |
27 ms |
40152 KB |
Output is correct |
| 3 |
Incorrect |
27 ms |
40276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
523 ms |
151816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
523 ms |
151816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
40148 KB |
Output is correct |
| 2 |
Correct |
37 ms |
42188 KB |
Output is correct |
| 3 |
Correct |
37 ms |
42208 KB |
Output is correct |
| 4 |
Incorrect |
37 ms |
40584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
