| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1067982 |
2024-08-21T06:23:25 Z |
정민찬(#11128) |
Paths (RMI21_paths) |
C++17 |
|
43 ms |
14160 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];
void dfs3(ll x, ll p) {
for (auto &[y, c] : adj[x]) {
if (y == p) continue;
par[y] = x;
dist1[y] = dist1[x] + c;
dist2[y] = dist2[x] + 1;
dfs3(y, x);
}
}
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});
}
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;
}
dist1[1] = dist2[1] = 0;
dfs3(1, 0);
pll mx = {-1, -1};
ll r1 = -1;
for (ll i=1; i<=N; i++) {
if (mx < pll{dist1[i], dist2[i]}) {
mx = {dist1[i], dist2[i]};
r1 = i;
}
}
dist1[r1] = dist2[r1] = 0;
par[r1] = 0;
dfs3(r1, 0);
mx = {-1, -1}; ll r2 = -1;
for (ll i=1; i<=N; i++) {
if (mx < pll{dist1[i], dist2[i]}) {
mx = {dist1[i], dist2[i]};
r2 = i;
}
}
assert(r1 != r2);
ll x = r2;
pll diff = {inf, inf};
ll mid = -1;
while (x) {
pll cur = {abs(dist1[x] - (dist1[r2] - dist1[x])), abs(dist2[x] - (dist2[r2] - dist2[x]))};
if (cur < diff) {
diff = cur;
mid = x;
}
x = par[x];
}
assert(adj[mid].size() >= 2);
//cout << mid << '\n';
par[mid] = 0;
dist1[mid] = 0;
dfs4(mid, 0);
seg.init(pv - 1);
ll sum = dist1[r1] + dist1[r2];
assert(seg.tree[1].first == max(dist1[r1], dist1[r2]));
seg.del(1, 1, pv-1, in[r1]);
Ers(r1);
//assert(seg.tree[1].first == min(dist1[r1], dist1[r2]));
seg.del(1, 1, pv-1, in[r2]);
Ers(r2);
vector<ll> ch = {r1, r2};
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:103:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
103 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::build(ll, ll, ll)':
Main.cpp:114:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:135:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
135 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'void SegmentTree::del(ll, ll, ll, ll)':
Main.cpp:147:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
147 | ll mid = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'pll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:156:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
156 | ll mid = s + e >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
43 ms |
12708 KB |
Output is correct |
| 2 |
Correct |
43 ms |
14160 KB |
Output is correct |
| 3 |
Correct |
41 ms |
12376 KB |
Output is correct |
| 4 |
Correct |
41 ms |
12496 KB |
Output is correct |
| 5 |
Correct |
42 ms |
13228 KB |
Output is correct |
| 6 |
Correct |
42 ms |
12360 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
