#include <bits/stdc++.h>
#include "roads.h"
using namespace std;
const int N = 1e5;
int k, deg[N], dp[N][2];
long long sum[N], f[N];
multiset<long long> s[N][2];
vector<pair<int, int>> preAdj[N], adj[N];
bool mark[N], vst[N];
void Add(int u, long long val0, long long val1) {
val1 = min(val1, val0);
sum[u] += val0;
f[u] += val1 - val0;
s[u][0].insert(val1 - val0);
}
void Del(int u, long long val0, long long val1) {
val1 = min(val1, val0);
sum[u] -= val0;
if (s[u][0].find(val1 - val0) != s[u][0].end()) {
f[u] -= val1 - val0;
s[u][0].erase(s[u][0].find(val1 - val0));
} else {
s[u][1].erase(s[u][1].find(val1 - val0));
}
}
void Fix(int u, int sz) {
while((int) s[u][0].size() > sz) {
long long x = *s[u][0].rbegin();
f[u] -= x;
s[u][0].erase(s[u][0].find(x));
s[u][1].insert(x);
}
while((int) s[u][0].size() < sz && !s[u][1].empty()) {
long long x = *s[u][1].begin();
f[u] += x;
s[u][1].erase(s[u][1].find(x));
s[u][0].insert(x);
}
}
void Dfs(int u, int p) {
vst[u] = 1;
vector<pair<long long, long long>> vals;
for(auto e : adj[u]) {
int v = e.first;
int w = e.second;
if (v == p)
continue;
Dfs(v, u);
vals.push_back({dp[v][1] + w, dp[v][0]});
}
for(auto p : vals)
Add(u, p.first, p.second);
Fix(u, k);
dp[u][1] = sum[u] + f[u];
dp[u][0] = sum[u] + (f[u] - *s[u][0].rbegin());
for(auto p : vals)
Del(u, p.first, p.second);
}
vector<long long> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
k = n;
vector<int> ord(n);
for(int i = 0; i < n - 1; i++) {
deg[u[i]]++;
deg[v[i]]++;
Add(u[i], w[i], 0);
Add(v[i], w[i], 0);
preAdj[u[i]].push_back({v[i], w[i]});
preAdj[v[i]].push_back({u[i], w[i]});
}
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int &u, const int &v) {
return deg[u] > deg[v];
});
vector<long long> res(n, 0);
int ptr = 0;
for(k = n - 1; k >= 1; k--) {
while(ptr < n && deg[ord[ptr]] > k) {
int u = ord[ptr++];
mark[u] = 1;
for(auto e : preAdj[u]) {
int v = e.first;
int w = e.second;
if (!mark[v])
continue;
Del(u, w, 0);
Del(v, w, 0);
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
memset(vst, 0, sizeof(vst));
for(int u = 0; u < n; u++)
if (mark[u] && !vst[u]) {
Dfs(u, -1);
res[k] += dp[u][1];
}
}
res[0] = accumulate(w.begin(), w.end(), 0ll);
return res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Incorrect |
25 ms |
14796 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14500 KB |
Output is correct |
2 |
Execution timed out |
2072 ms |
29328 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14484 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Incorrect |
11 ms |
14512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
9 ms |
14484 KB |
Output is correct |
3 |
Correct |
10 ms |
14412 KB |
Output is correct |
4 |
Incorrect |
11 ms |
14512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2067 ms |
33044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2067 ms |
33044 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Incorrect |
25 ms |
14796 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |