#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
const int MAXN = 1e5;
vector<pair<int, int>> adj[MAXN];
vector<int> prefSum[MAXN];
bool seen[MAXN];
// [withPar, withoutPar]
pair<int, int> dfs(int u, int p, int maxDeg) {
assert(!seen[u]);
seen[u] = true;
int coutInit = 0;
vector<int> swaps;
for (auto [v, w] : adj[u])
if (v != p) {
if ((int)adj[v].size() <= maxDeg) {
swaps.push_back(w);
continue;
}
auto [withPar, withoutPar] = dfs(v, u, maxDeg);
coutInit += withPar;
assert(coutInit < INF);
swaps.push_back(withoutPar + w - withPar);
}
sort(swaps.begin(), swaps.end());
// withPar :
int toRem = adj[u].size() - maxDeg;
int withPar = INF;
if (toRem <= 0)
withPar = coutInit;
int accu = coutInit;
if (toRem > 0)
for (int i = 0; i < (int)swaps.size(); ++i) {
accu += swaps[i];
if (i + 1 >= toRem) {
withPar = min(withPar, accu);
// break;
}
}
// withoutPar
toRem = adj[u].size() - maxDeg - (u != p);
int withoutPar = INF;
if (toRem <= 0)
withoutPar = coutInit;
accu = coutInit;
if (toRem > 0)
for (int i = 0; i < (int)swaps.size(); ++i) {
accu += swaps[i];
if (i + 1 >= toRem) {
withoutPar = min(withoutPar, accu);
// break;
}
}
return pair(withPar, withoutPar);
}
vector<int> minimum_closure_costs(signed N, vector<signed> U, vector<signed> V,
vector<signed> W) {
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<int> order(N);
iota(order.begin(), order.end(), 0LL);
sort(order.begin(), order.end(),
[&](int i, int j) { return adj[i].size() > adj[j].size(); });
for (int i = 0; i < N; ++i) {
sort(adj[i].begin(), adj[i].end(), [&](auto u, auto v) {
return adj[u.first].size() < adj[v.first].size();
});
prefSum[i].resize(adj[i].size() + 1);
for (int j = 0; j < (int)adj[i].size(); ++j)
prefSum[i][j + 1] = prefSum[i][j] + adj[i][j].second;
}
vector<int> ret(N);
ret[0] = accumulate(W.begin(), W.end(), 0LL);
for (int k = 1; k < N; ++k) {
for (int i : order) {
if ((int)adj[i].size() <= k)
break;
if (!seen[i])
ret[k] += dfs(i, i, k).first;
}
for (int i : order) {
if ((int)adj[i].size() <= k)
break;
seen[i] = false;
}
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
152 ms |
5352 KB |
Output is correct |
3 |
Correct |
164 ms |
5264 KB |
Output is correct |
4 |
Correct |
57 ms |
5252 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 |
62 ms |
5224 KB |
Output is correct |
9 |
Correct |
88 ms |
5256 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Execution timed out |
2083 ms |
13664 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Incorrect |
59 ms |
22620 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
17292 KB |
Output is correct |
2 |
Correct |
105 ms |
17136 KB |
Output is correct |
3 |
Correct |
570 ms |
18584 KB |
Output is correct |
4 |
Correct |
114 ms |
17688 KB |
Output is correct |
5 |
Correct |
546 ms |
18692 KB |
Output is correct |
6 |
Execution timed out |
2083 ms |
17604 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
17292 KB |
Output is correct |
2 |
Correct |
105 ms |
17136 KB |
Output is correct |
3 |
Correct |
570 ms |
18584 KB |
Output is correct |
4 |
Correct |
114 ms |
17688 KB |
Output is correct |
5 |
Correct |
546 ms |
18692 KB |
Output is correct |
6 |
Execution timed out |
2083 ms |
17604 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
152 ms |
5352 KB |
Output is correct |
3 |
Correct |
164 ms |
5264 KB |
Output is correct |
4 |
Correct |
57 ms |
5252 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 |
62 ms |
5224 KB |
Output is correct |
9 |
Correct |
88 ms |
5256 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Execution timed out |
2083 ms |
13664 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |