| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 954372 |
2024-03-27T17:34:12 Z |
TAhmed33 |
Paths (RMI21_paths) |
C++ |
|
600 ms |
17464 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 1e5 + 25;
vector <pair <int, ll>> adj[MAXN];
pair <ll, ll> dp[MAXN], dq[MAXN];
ll edge[MAXN];
int n, k;
void dfs (int pos, int par) {
if ((int)adj[pos].size() == 1) {
dp[pos] = {edge[pos], pos};
return;
}
for (auto j : adj[pos]) {
if (j.first == par) continue;
edge[j.first] = j.second;
dfs(j.first, pos);
dp[pos] = max(dp[pos], dp[j.first]);
}
dp[pos].first += edge[pos];
}
void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
dq[pos] = {x.first + edge[pos], x.second};
deque <pair <ll, ll>> u;
for (auto j : adj[pos]) {
if (j.first == par) continue;
u.push_back(dp[j.first]);
}
for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
for (auto j : adj[pos]) {
if (j.first == par) continue;
u.pop_front();
auto g = x; if (!u.empty()) g = max(g, u.front());
dfs2(j.first, pos, max(x, g));
x = max(g, dp[j.first]);
}
}
struct DS {
ll val[MAXN];
void upd (int a, ll b) {
val[a] += b;
}
ll get () {
vector <ll> d;
for (int i = 1; i <= n; i++) d.push_back(val[i]);
sort(d.begin(), d.end());
reverse(d.begin(), d.end());
ll sum = 0;
for (int i = 0; i < k; i++) sum += d[i];
return sum;
}
void init () {
for (int i = 1; i <= n; i++) {
val[i] = -inf;
}
}
} cur;
ll ans[MAXN];
void dfs3 (int pos, int par) {
if (par != -1) {
cur.upd(dp[pos].second, -edge[pos]);
cur.upd(dq[pos].second, edge[pos]);
}
ans[pos] = cur.get();
for (auto j : adj[pos]) {
if (j.first != par) {
dfs3(j.first, pos);
}
}
if (par != -1) {
cur.upd(dq[pos].second, -edge[pos]);
cur.upd(dp[pos].second, edge[pos]);
}
}
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
if (n == 1) {
cout << "0\n";
return 0;
}
if (n == 2) {
int a, b, c; cin >> a >> b >> c;
cout << c << " " << c << '\n';
return 0;
}
for (int i = 1; i < n; i++) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
int root = -1;
for (int i = 1; i <= n; i++) {
if ((int)adj[i].size() >= 2) root = i;
}
//cout << root << '\n';
dfs(root, -1);
dfs2(root, -1);
/*for (int i = 1; i <= n; i++) {
cout << i << " " << edge[i] << ": ";
cout << dp[i].first << " " << dp[i].second << " || " << dq[i].first << " " << dq[i].second << '\n';
}*/
cur.init();
for (int i = 1; i <= n; i++) {
if ((int)adj[i].size() == 1) {
cur.upd(i, inf);
}
}
for (int i = 1; i <= n; i++) {
if (i != root) {
cur.upd(dp[i].second, edge[i]);
}
}
dfs3(root, -1);
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1054 ms |
17464 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8028 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
8028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
