| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 849357 |
2023-09-14T14:14:00 Z |
luanmenglei |
Paths (RMI21_paths) |
C++17 |
|
195 ms |
21172 KB |
#include <bits/stdc++.h>
using namespace std;
void debug(const char *msg, ...) {
#ifdef CLESIP
va_list arg;
static char pbString[512];
va_start(arg,msg);
vsprintf(pbString,msg,arg);
cerr << "[DEBUG] " << pbString << "\n";
va_end(arg);
#endif
}
using i64 = long long;
const int N = 1e5 + 10;
vector<pair<int, int>> G[N];
int n, k, top[N], dfn[N], cnt, sze[N];
i64 sum[N], val[N], res, ans[N];
bool v[N];
pair<i64, int> son[N], seson[N], oson[N];
set<pair<i64, int>> s, os;
void dfs1(int x, int fa) {
dfn[x] = ++ cnt, sze[x] = 1;
if (G[x].size() == 1) {
son[x] = { sum[x], x };
return;
}
for (auto [y, z] : G[x]) if (y != fa) {
sum[y] = sum[x] + z;
dfs1(y, x);
sze[x] += sze[y];
if (son[x] < son[y]) {
seson[x] = son[x];
son[x] = son[y];
if (seson[x] < seson[y])
seson[x] = seson[y];
} else if (seson[x] < son[y]) {
seson[x] = son[y];
}
}
}
bool in_subtree(int x, int y) { return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + sze[x]; }
void dfs2(int x, int fa) {
for (auto [y, z] : G[x]) if (y != fa) {
top[son[y].second] = x;
if (in_subtree(y, son[x].second)) {
oson[y] = max(oson[x], seson[x]);
dfs2(y, x);
} else {
oson[y] = max(oson[x], son[x]);
dfs2(y, x);
}
}
if (son[x].second) top[son[x].second] = fa;
}
void update(int x, i64 d) {
if (v[x]) {
auto it = s.find({ val[x], x });
s.erase(it), res -= val[x];
val[x] += d;
if (!os.empty() && prev(os.end()) -> first > val[x]) {
it = prev(os.end());
s.insert(*it), res += it -> first, v[it -> second] = true;
os.erase(it);
os.emplace(val[x], x), v[x] = false;
} else {
s.emplace(val[x], x), res += val[x];
}
} else {
auto it = os.find({ val[x], x });
os.erase(it);
val[x] += d;
if ((int) s.size() < k || s.begin()->first < val[x]) {
it = s.begin();
res -= it -> first, os.insert(*it), v[it -> second] = false;
s.erase(it);
s.emplace(val[x], x), res += val[x], v[x] = true;
} else {
os.emplace(val[x], x);
}
}
}
void dfs3(int x, int fa) {
ans[x] = res;
for (auto [y, z] : G[x]) if (y != fa) {
update(son[y].second, -z);
update(oson[y].second, z);
dfs3(y, x);
update(son[y].second, z);
update(oson[y].second, -z);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1, x, y, z; i < n; i ++) {
cin >> x >> y >> z;
G[x].emplace_back(y, z);
G[y].emplace_back(x, z);
}
dfs1(1, 0), dfs2(1, 0);
for (int i = 1; i <= n; i ++) if (G[i].size() == 1) {
val[i] = sum[i] - sum[top[i]];
s.emplace(val[i], i);
v[i] = true, res += val[i];
if ((int) s.size() > k) {
auto it = s.begin();
v[it -> second] = false, res -= it -> first;
os.insert(*it), s.erase(it);
}
}
dfs3(1, 0);
for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
195 ms |
21172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
