#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MN = 1e5+5;
int N, sz[MN]; vector<pair<int,int>> adjl[MN]; ll ans[MN]; vector<ll> diffs[MN];
struct KMin{
multiset<ll> st; int k;
void init(int _k){ st.clear(); k = _k; }
void insert(ll x){ st.insert(x); }
void erase(ll x){ st.erase(st.find(x)); }
void decK(){ assert(k--); }
ll query(){
assert(st.size() >= k);
ll ret = 0;
int i = 0;
for(auto it = st.begin(); i < k; i++, it++)
ret += *it;
return ret;
}
} kMin;
void dfs(int u){
sort(adjl[u].begin(), adjl[u].end(), [](pair<int,int> lhs, pair<int,int> rhs){
return sz[lhs.first] > sz[rhs.first];
});
for(auto [v, w]: adjl[u]){
adjl[v].erase(find(adjl[v].begin(), adjl[v].end(), pair(u, w)));
dfs(v);
}
diffs[u].resize(sz[u]);
kMin.init(sz[u] - 1);
for(auto [v, w]: adjl[u])
kMin.insert(w);
for(int k = 1; k < sz[u]; k++){
for(auto [v, w]: adjl[u]){
if(sz[v] <= k) break;
kMin.erase(w);
if(diffs[v][k] > w)
ans[k] += w - diffs[v][k];
kMin.insert(max(0LL, w - diffs[v][k]));
}
assert(kMin.k == sz[u] - k);
ll res1 = kMin.query();
kMin.decK();
ll res2 = kMin.query();
ans[k] += res1;
diffs[u][k] = res1 - res2;
for(auto [v, w]: adjl[u]){
if(sz[v] <= k) break;
kMin.insert(w);
kMin.erase(max(0LL, w - diffs[v][k]));
}
}
}
vector<ll> minimum_closure_costs(int _N, vector<int> us, vector<int> vs,
vector<int> ws){
N = _N;
for(int i = 0, u, v, w; i < N-1; i++){
u = us[i]; v = vs[i]; w = ws[i];
adjl[u].emplace_back(v, w);
adjl[v].emplace_back(u, w);
}
for(int i = 0; i < N; i++)
sz[i] = adjl[i].size();
++sz[0];
dfs(0);
ans[0] = accumulate(ws.begin(), ws.end(), 0LL);
for(int k = 1; k < sz[0]; k++)
ans[k] -= diffs[0][k];
return vector<ll>(ans, ans+N);
}
#ifdef LOCAL_PROJECT
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N; cin >> N;
vector<int> us(N-1), vs(N-1), ws(N-1);
for(int i = 0; i < N-1; i++)
cin >> us[i] >> vs[i] >> ws[i];
vector<ll> ans = minimum_closure_costs(N, us, vs, ws);
for(int i = 0; i < N; i++)
printf("%d%c", ans[i], " \n"[i==N-1]);
return 0;
}
#endif
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from roads.cpp:1:
roads.cpp: In member function 'll KMin::query()':
roads.cpp:16:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
16 | assert(st.size() >= k);
| ~~~~~~~~~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
37 ms |
5296 KB |
Output is correct |
3 |
Correct |
41 ms |
5312 KB |
Output is correct |
4 |
Correct |
25 ms |
5324 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
4 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
27 ms |
5272 KB |
Output is correct |
9 |
Correct |
32 ms |
5324 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Execution timed out |
2094 ms |
14192 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
68 ms |
23440 KB |
Output is correct |
3 |
Correct |
84 ms |
27856 KB |
Output is correct |
4 |
Correct |
99 ms |
29332 KB |
Output is correct |
5 |
Correct |
79 ms |
29516 KB |
Output is correct |
6 |
Correct |
5 ms |
5332 KB |
Output is correct |
7 |
Correct |
4 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5400 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
3 ms |
4948 KB |
Output is correct |
12 |
Correct |
46 ms |
19156 KB |
Output is correct |
13 |
Correct |
68 ms |
28568 KB |
Output is correct |
14 |
Correct |
3 ms |
5008 KB |
Output is correct |
15 |
Correct |
65 ms |
26280 KB |
Output is correct |
16 |
Correct |
84 ms |
28568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
15108 KB |
Output is correct |
2 |
Correct |
98 ms |
14972 KB |
Output is correct |
3 |
Correct |
256 ms |
16768 KB |
Output is correct |
4 |
Correct |
101 ms |
15360 KB |
Output is correct |
5 |
Correct |
269 ms |
16880 KB |
Output is correct |
6 |
Correct |
1081 ms |
16576 KB |
Output is correct |
7 |
Correct |
197 ms |
16000 KB |
Output is correct |
8 |
Execution timed out |
2083 ms |
19144 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
15108 KB |
Output is correct |
2 |
Correct |
98 ms |
14972 KB |
Output is correct |
3 |
Correct |
256 ms |
16768 KB |
Output is correct |
4 |
Correct |
101 ms |
15360 KB |
Output is correct |
5 |
Correct |
269 ms |
16880 KB |
Output is correct |
6 |
Correct |
1081 ms |
16576 KB |
Output is correct |
7 |
Correct |
197 ms |
16000 KB |
Output is correct |
8 |
Execution timed out |
2083 ms |
19144 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
37 ms |
5296 KB |
Output is correct |
3 |
Correct |
41 ms |
5312 KB |
Output is correct |
4 |
Correct |
25 ms |
5324 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
4 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
27 ms |
5272 KB |
Output is correct |
9 |
Correct |
32 ms |
5324 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Execution timed out |
2094 ms |
14192 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |