| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1068066 |
2024-08-21T07:04:57 Z |
정민찬(#11128) |
Paths (RMI21_paths) |
C++17 |
|
69 ms |
12116 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];
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 mx1 = 0, mx2 = 0;
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
if (mx1 < down[y] + c) {
mx2 = mx1; mx1 = down[y] + c;
}
else if (mx2 < down[y] + c) {
mx2 = down[y] + c;
}
}
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
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);
}
}
void case1() {
dfs1(1, 0);
dfs2(1, 0);
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], dist2[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);
}
}
pll solve(ll mid) {
//cout << mid << '\n';
memset(vis, 0, sizeof(vis));
par[mid] = 0;
parc[mid] = 0;
dist1[mid] = 0;
pv = 1;
dfs4(mid, 0);
seg.init(pv - 1);
ll sum = 0;
ll id = seg.tree[1].second;
sum += seg.tree[1].first;
seg.del(1, 1, pv-1, id);
Ers(inv[id]);
ll mx = seg.tree[1].first, mx2 = -1;
ll nid;
for (auto &[y, c] : adj[mid]) {
if (in[y] <= id && id < out[y]) continue;
pll ret = seg.query(1, 1, pv-1, in[y], out[y]-1);
if (ret.first > mx2) {
mx2 = ret.first;
nid = ret.second;
}
}
if (mx2 < mx) {
return {id, seg.tree[1].second};
}
sum += mx2;
seg.del(1, 1, pv-1, nid);
Ers(inv[nid]);
vector<ll> ch = {inv[id], inv[nid]};
for (ll rep=0; rep<K-2; rep++) {
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';
}
exit(0);
}
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});
}
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;
}
for (ll i=1; i<=N; i++) {
solve(i);
}
assert(0);
ll mid;
for (ll i=1; i<=N; i++) {
if (adj[i].size() >= 2) {
mid = i;
break;
}
}
}
Compilation message
Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:93:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
93 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::build(ll, ll, ll)':
Main.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:125:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
125 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::del(ll, ll, ll, ll)':
Main.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
137 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'pll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:146:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
146 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:251:8: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
251 | ll mid;
| ^~~
Main.cpp: In function 'pll solve(ll)':
Main.cpp:138:6: warning: 'nid' may be used uninitialized in this function [-Wmaybe-uninitialized]
138 | del(node*2, s, mid, tar);
| ~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:188:5: note: 'nid' was declared here
188 | ll nid;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
39 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
48 ms |
12116 KB |
Output is correct |
| 3 |
Correct |
69 ms |
10320 KB |
Output is correct |
| 4 |
Correct |
40 ms |
10444 KB |
Output is correct |
| 5 |
Correct |
47 ms |
11344 KB |
Output is correct |
| 6 |
Correct |
41 ms |
10324 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
3420 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
