#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
typedef long long ll;
struct fenwick {
vector<ll> t;
int n;
fenwick() = default;
fenwick(int x) {
n = x + 1;
t.assign(n, 0);
}
void init(int x) {
n = x + 1;
t.assign(n, 0);
}
void add(int i, int x) {
i += 1;
for (; i < n; i += i & -i)
t[i] += x;
}
ll get(int i) {
ll ans = 0;
i += 1;
for (; i > 0; i -= i & -i)
ans += t[i];
return ans;
}
int kth(int k) {
if (k == 0) return -1;
int i = 0;
for (int j = 18; j > -1; --j) {
if (i + (1 << j) < n && t[i + (1 << j)] < k) {
i += (1 << j);
k -= t[i];
}
}
return i;
}
};
const int N = 100001;
int A[N], B[N], W[N], n, par[N], sz[N], wp[N], depth[N];
vector<pair<int, int>> g[N], gr[N];
fenwick f1[N], f2[N];
bool used[N];
ll dp[2][N], sm[N];
vector<ll> minimum_closure_costs(int nn, vector<int> uu, vector<int> vv, vector<int> ww) {
n = nn;
for (int i = 0; i < n - 1; ++i) {
A[i] = uu[i], B[i] = vv[i], W[i] = ww[i];
gr[A[i]].emplace_back(-W[i], B[i]);
gr[B[i]].emplace_back(-W[i], A[i]);
}
for (int i = 0; i < n; ++i) {
sort(all(gr[i]));
sz[i] = (int) size(gr[i]);
f1[i].init(sz[i]);
f2[i].init(sz[i]);
}
vector<int> ord(n);
iota(all(ord), 0);
sort(all(ord), [](int i, int j) {
return sz[i] > sz[j];
});
function<void(int, int, int)> prec = [&prec](int v, int p, int wep){
par[v] = p;
wp[v] = wep;
for (auto [w, to] : gr[v]) {
if (to != p) {
depth[to] = depth[v] + 1;
prec(to, v, -w);
}
}
};
vector<ll> ans(n);
prec(0, -1, 0);
for (int k = 0; k < n; ++k) {
vector<int> now;
for (int i : ord) {
if (sz[i] < k) break;
if (sz[i] == k) {
for (auto [w, to] : gr[i]) {
if (sz[to] <= sz[i]) continue;
int id = lower_bound(all(gr[to]), make_pair(w, i)) - begin(gr[to]);
f1[to].add(id, 1);
f2[to].add(id, -w);
sm[to] += -w;
}
continue;
}
now.push_back(i);
used[i] = true;
}
for (int x : now) {
if (par[x] != -1 && used[par[x]]) {
g[par[x]].emplace_back(x, wp[x]);
}
}
for (int x : now) used[x] = false;
function<void(int, int)> dfs = [&](int v, int p) {
used[v] = true;
vector<pair<int, int>> adj;
for (auto [to, w] : g[v]) {
if (to != p) {
dfs(to, v);
adj.emplace_back(to, w);
}
}
vector<ll> nw;
ll sum = 0;
for (auto [to, w] : adj) {
nw.push_back(dp[1][to] - dp[0][to] - w);
sum += dp[0][to] + w;
}
sort(all(nw));
const ll infL = 3e18;
dp[1][v] = dp[0][v] = infL;
for (int take = 0; take <= min(k, (int)size(nw)); ++take) {
if (take) {
sum += nw[take - 1];
}
if (take < k) {
int there = k - take - 1;
int id = f1[v].kth(there);
ll added = sm[v] - f2[v].get(id);
dp[1][v] = min(dp[1][v], sum + added);
}
int id = f1[v].kth(k - take);
ll added = sm[v] - f2[v].get(id);
dp[0][v] = min(dp[0][v], sum + added);
}
dp[0][v] = min(dp[0][v], dp[1][v]);
};
sort(all(now), [](int i, int j) {
return depth[i] < depth[j];
});
for (int v : now) {
if (!used[v]) {
dfs(v, -1);
ans[k] += dp[0][v];
}
}
for (int v : now) {
used[v] = false;
g[v].clear();
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
9 ms |
11732 KB |
Output is correct |
3 |
Correct |
8 ms |
11732 KB |
Output is correct |
4 |
Correct |
10 ms |
11860 KB |
Output is correct |
5 |
Correct |
7 ms |
11280 KB |
Output is correct |
6 |
Correct |
6 ms |
11356 KB |
Output is correct |
7 |
Correct |
7 ms |
11348 KB |
Output is correct |
8 |
Correct |
10 ms |
11732 KB |
Output is correct |
9 |
Correct |
10 ms |
11708 KB |
Output is correct |
10 |
Correct |
6 ms |
11348 KB |
Output is correct |
11 |
Correct |
6 ms |
11280 KB |
Output is correct |
12 |
Correct |
76 ms |
25824 KB |
Output is correct |
13 |
Correct |
133 ms |
35624 KB |
Output is correct |
14 |
Correct |
138 ms |
33728 KB |
Output is correct |
15 |
Correct |
146 ms |
36088 KB |
Output is correct |
16 |
Correct |
170 ms |
36364 KB |
Output is correct |
17 |
Correct |
149 ms |
36464 KB |
Output is correct |
18 |
Correct |
7 ms |
11220 KB |
Output is correct |
19 |
Correct |
113 ms |
33472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11280 KB |
Output is correct |
2 |
Incorrect |
109 ms |
47744 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
8 ms |
11280 KB |
Output is correct |
4 |
Incorrect |
8 ms |
11316 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
6 ms |
11220 KB |
Output is correct |
3 |
Correct |
8 ms |
11280 KB |
Output is correct |
4 |
Incorrect |
8 ms |
11316 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
34080 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
34080 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11220 KB |
Output is correct |
2 |
Correct |
9 ms |
11732 KB |
Output is correct |
3 |
Correct |
8 ms |
11732 KB |
Output is correct |
4 |
Correct |
10 ms |
11860 KB |
Output is correct |
5 |
Correct |
7 ms |
11280 KB |
Output is correct |
6 |
Correct |
6 ms |
11356 KB |
Output is correct |
7 |
Correct |
7 ms |
11348 KB |
Output is correct |
8 |
Correct |
10 ms |
11732 KB |
Output is correct |
9 |
Correct |
10 ms |
11708 KB |
Output is correct |
10 |
Correct |
6 ms |
11348 KB |
Output is correct |
11 |
Correct |
6 ms |
11280 KB |
Output is correct |
12 |
Correct |
76 ms |
25824 KB |
Output is correct |
13 |
Correct |
133 ms |
35624 KB |
Output is correct |
14 |
Correct |
138 ms |
33728 KB |
Output is correct |
15 |
Correct |
146 ms |
36088 KB |
Output is correct |
16 |
Correct |
170 ms |
36364 KB |
Output is correct |
17 |
Correct |
149 ms |
36464 KB |
Output is correct |
18 |
Correct |
7 ms |
11220 KB |
Output is correct |
19 |
Correct |
113 ms |
33472 KB |
Output is correct |
20 |
Correct |
6 ms |
11280 KB |
Output is correct |
21 |
Incorrect |
109 ms |
47744 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |