| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 871099 |
2023-11-09T21:57:51 Z |
MinaRagy06 |
Paths (RMI21_paths) |
C++17 |
|
600 ms |
15228 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100'005;
vector<array<int, 2>> adj[N];
int n, k;
ll vals[N];
pair<ll, int> dp[N][2];
void dfs(int i, int par, int parc) {
dp[i][0] = dp[i][1] = {-1e18, 0};
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, w);
pair<ll, int> nxtval = dp[nxt][0];
nxtval.first += w;
if (nxtval > dp[i][1]) {
dp[i][1] = nxtval;
}
if (dp[i][0] < dp[i][1]) {
swap(dp[i][0], dp[i][1]);
}
}
if (adj[i].size() == 1) {
dp[i][0] = {0, i};
}
vals[dp[i][0].second] += parc;
}
ll ans[N];
ll calc() {
vector<ll> cur;
for (int i = 1; i <= n; i++) {
cur.push_back(vals[i]);
}
sort(cur.rbegin(), cur.rend());
ll sum = 0;
for (int i = 0; i < k; i++) {
sum += cur[i];
}
return sum;
}
void dfs2(int i, int par, int parc, pair<ll, int> dpup) {
dpup.first += parc;
vals[dp[i][0].second] -= parc;
ans[i] = calc();
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
pair<ll, int> mx = dp[i][0];
if (dp[i][0] == dp[nxt][0]) mx = dp[i][1];
mx = max(mx, dpup);
vals[mx.second] += w;
dfs2(nxt, i, w, mx);
vals[mx.second] -= w;
}
vals[dp[i][0].second] += parc;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1, 0, 0);
dfs2(1, 0, 0, {0, 0});
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1010 ms |
15228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
