| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1068037 |
2024-08-21T06:50:07 Z |
정민찬(#11128) |
Paths (RMI21_paths) |
C++17 |
|
154 ms |
25388 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll inf = 2e18;
vector<pll> adj[100010];
vector<array<ll,3>> go[100010];
ll down[100010];
ll up[100010];
ll N, K;
void dfs1(ll x, ll p) {
down[x] = 0;
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
dfs1(y, x);
down[x] = max(down[x], down[y] + c);
}
}
void dfs2(ll x, ll p, ll C) {
ll mx1 = -1, mx2 = -1, mx3 = -1;
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
if (mx1 < down[y] + c) {
mx3 = mx2;
mx2 = mx1;
mx1 = down[y] + c;
}
else if (mx2 < down[y] + c) {
mx3 = mx2;
mx2 = down[y] + c;
}
else if (mx3 < down[y] + c) {
mx3 = down[y] + c;
}
}
go[p].push_back({x, mx1 + C, mx2});
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
vector<ll> cand;
if (mx1 == down[y] + c) cand = {mx2, mx3};
else if (mx2 == down[y] + c) cand = {mx1, mx3};
else cand = {mx1, mx2};
cand.push_back(up[x]);
sort(cand.begin(), cand.end());
go[y].push_back({x, cand[2] + c, cand[1]});
up[y] = up[x] + c;
if (mx1 == down[y] + c) up[y] = max(up[y], mx2 + c);
else up[y] = max(up[y], mx1 + c);
dfs2(y, x, c);
}
}
void case1() {
/*for (ll i=1; i<=N; i++) {
cout << up[i] << ' ' << down[i] << '\n';
for (auto &[j, mx1, mx2] : go[i]) {
cout << '(' << j << ',' << mx1 << ',' << mx2 << ") ";
}
cout << '\n';
}*/
for (ll i=1; i<=N; i++) {
cout << max(up[i], down[i]) << '\n';
}
}
void case2() {
ll tot = 0;
for (ll i=1; i<=N; i++) {
for (auto &[j, c] : adj[i]) {
if (i < j) tot += c;
}
}
for (ll i=1; i<=N; i++) {
cout << tot << '\n';
}
}
ll dist1[100010];
ll par[100010];
ll in[100010], out[100010];
ll pv = 1;
ll inv[100010];
ll parc[100010];
void dfs4(ll x, ll p) {
in[x] = pv;
if (p && adj[x].size() == 1) {
inv[pv] = x;
pv ++;
}
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
par[y] = x;
parc[y] = c;
dist1[y] = dist1[x] + c;
dfs4(y, x);
}
out[x] = pv;
}
struct SegmentTree{
vector<pll> tree;
vector<ll> lazy;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.resize(sz);
lazy.resize(sz);
build(1, 1, n);
}
void build(ll node, ll s, ll e) {
lazy[node] = 0;
if (s == e) {
tree[node] = {dist1[inv[s]], s};
return;
}
ll mid = s + e >> 1;
build(node*2, s, mid);
build(node*2+1, mid+1, e);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
void propagate(ll node, ll s, ll e) {
tree[node].first -= lazy[node];
if (s != e) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
void update(ll node, ll s, ll e, ll l, ll r, ll v) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = v;
propagate(node, s, e);
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, l, r, v);
update(node*2+1, mid+1, e, l, r, v);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
void del(ll node, ll s, ll e, ll tar) {
propagate(node, s, e);
if (s > tar || tar > e) return;
if (s == e) {
tree[node] = {-inf, -1};
return;
}
ll mid = s + e >> 1;
del(node*2, s, mid, tar);
del(node*2+1, mid+1, e, tar);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
pll query(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return {-inf, -1};
if (l <= s && e <= r) return tree[node];
ll mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
SegmentTree seg;
ll vis[100010];
void Ers(ll x) {
while (x && !vis[x]) {
seg.update(1, 1, pv-1, in[x], out[x]-1, parc[x]);
vis[x] = 1;
x = par[x];
}
}
ll ans[100010];
void dfs5(ll x, ll p) {
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
if (vis[y]) ans[y] = ans[x];
else ans[y] = ans[x] + c;
dfs5(y, x);
}
}
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
cin >> N >> K;
for (ll i=0; i<N-1; i++) {
ll u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
dfs1(1, 0);
dfs2(1, 0, 0);
if (K == 1) {
case1();
return 0;
}
ll leaf = 0;
for (ll i=1; i<=N; i++) {
if (adj[i].size() <= 1)
leaf ++;
}
if (leaf <= K) {
case2();
return 0;
}
ll mid = -1, r1, r2;
for (ll i=1; i<=N; i++) {
if (adj[i].size() == 1) continue;
sort(go[i].begin(), go[i].end(), [&] (array<ll,3> &u, array<ll,3> &v) {
if (u[1] != v[1]) return u[1] > v[1];
return u[2] < v[2];
});
if (go[i][1][1] >= go[i][0][2]) {
mid = i;
r1 = go[i][0][0];
r2 = go[i][1][0];
break;
}
}
assert(mid != -1);
//cout << mid << '\n';
par[mid] = 0;
dist1[mid] = 0;
dfs4(mid, 0);
seg.init(pv - 1);
vector<ll> ch;
ll sum = 0;
pll ret = seg.query(1, 1, pv-1, in[r1], out[r1]-1);
assert(seg.tree[1].first == ret.first);
sum += ret.first;
seg.del(1, 1, pv-1, ret.second);
Ers(inv[ret.second]);
ch.push_back(inv[ret.second]);
ret = seg.query(1, 1, pv-1, in[r2], out[r2]-1);
assert(seg.tree[1].first == ret.first);
sum += ret.first;
seg.del(1, 1, pv-1, ret.second);
Ers(inv[ret.second]);
ch.push_back(inv[ret.second]);
for (ll rep=0; rep<K-2; rep++) {
ll id = seg.tree[1].second;
sum += seg.tree[1].first;
seg.del(1, 1, pv-1, id);
Ers(inv[id]);
ch.push_back(inv[id]);
}
ans[mid] = sum;
dfs5(mid, 0);
if (seg.tree[1].second != -1) {
sum += seg.tree[1].first;
for (auto &i : ch) {
ans[i] = sum;
}
}
for (ll i=1; i<=N; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:113:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
113 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::build(ll, ll, ll)':
Main.cpp:124:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
124 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:145:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
145 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::del(ll, ll, ll, ll)':
Main.cpp:157:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
157 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'pll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:166:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
166 | ll mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5216 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5216 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5216 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5216 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
21584 KB |
Output is correct |
| 2 |
Correct |
154 ms |
25388 KB |
Output is correct |
| 3 |
Correct |
63 ms |
21308 KB |
Output is correct |
| 4 |
Correct |
81 ms |
21256 KB |
Output is correct |
| 5 |
Correct |
74 ms |
23032 KB |
Output is correct |
| 6 |
Correct |
68 ms |
21060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5216 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
10068 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
