| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 736248 |
2023-05-05T11:07:39 Z |
flappybird |
Paths (RMI21_paths) |
C++17 |
|
113 ms |
15276 KB |
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<ll, int> pli;
vector<int> adj[MAX];
pii edges[MAX];
ll C[MAX];
int get_next(int x, int e) {
return edges[e].first + edges[e].second - x;
}
ll dep[MAX];
int prt[MAX];
pii range[MAX];
ll up[MAX];
int vis[MAX];
ll dis[MAX];
ll down[MAX];
ll mxp[MAX];
void get_down(int x, int p = 0) {
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
get_down(v, x);
down[x] = max(down[x], down[v] + C[e]);
}
}
void get_mxp(int x, int p = 0) {
pli mx1(0, 0), mx2(0, 0);
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
get_mxp(v, x);
up[v] = C[e];
mx2 = max(mx2, pli(down[v] + C[e], v));
if (mx2 > mx1) swap(mx1, mx2);
}
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
if (mx1.second == v) mxp[v] = mx2.first;
else mxp[v] = mx1.first;
}
}
ll upfar[MAX];
void get_upfar(int x, int p = 0) {
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
upfar[v] = max(upfar[x], mxp[v]) + C[e];
get_upfar(v, x);
}
}
void dfs(int x, int p = 0) {
if (!p) dep[x] = 0;
prt[x] = p;
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
dep[v] = dep[x] + C[e];
dfs(v, x);
}
}
int cnt;
int rev[MAX];
void make_range(int x, int p = 0) {
prt[x] = p;
cnt++;
range[x] = { cnt, cnt };
rev[range[x].first] = x;
for (auto e : adj[x]) {
int v = get_next(x, e);
if (v == p) continue;
up[v] = C[e];
make_range(v, x);
range[x].second = max(range[x].second, range[v].second);
}
}
namespace segtree {
pli tree[MAX * 4];
ll lazy[MAX * 4];
void init(int s, int e, int loc = 1) {
if (s == e) {
tree[loc].first = dep[rev[s]];
tree[loc].second = s;
return;
}
int m = s + e >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
}
void prop(int s, int e, int loc = 1) {
if (s == e) return;
for (auto c : { loc * 2, loc * 2 + 1 }) {
tree[c].first += lazy[loc];
lazy[c] += lazy[loc];
}
lazy[loc] = 0;
}
void upd(int s, int e, int l, int r, ll v, int loc = 1) {
if (e < l || r < s) return;
prop(s, e, loc);
if (l <= s && e <= r) {
tree[loc].first += v;
lazy[loc] += v;
return;
}
int m = s + e >> 1;
upd(s, m, l, r, v, loc * 2);
upd(m + 1, e, l, r, v, loc * 2 + 1);
tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
}
pli query(int s, int e, int l, int r, int loc = 1) {
if (r < s || e < l) return pli(0, 0);
prop(s, e, loc);
if (l <= s && e <= r) return tree[loc];
int m = s + e >> 1;
return max(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
}
}
ll getdis(int x) {
if (vis[x]) return 0;
if (dis[x]) return dis[x];
return dis[x] = getdis(prt[x]) + up[x];
}
ll ans[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, K;
cin >> N >> K;
if (N == 1) {
cout << 0 << ln;
return 0;
}
if (N == 2) {
int a, b, c;
cin >> a >> b >> c;
cout << c << ln << c << ln;
return 0;
}
int i;
for (i = 1; i < N; i++) cin >> edges[i].first >> edges[i].second >> C[i], adj[edges[i].first].push_back(i), adj[edges[i].second].push_back(i);
if (K == 1) {
dfs(1);
get_down(1);
get_mxp(1);
get_upfar(1);
for (i = 1; i <= N; i++) cout << max(down[i], upfar[i]) << ln;
return 0;
}
dfs(1);
int rt = 0;
for (i = 1; i <= N; i++) if (dep[rt] < dep[i]) rt = i;
dfs(rt);
int mx = 0;
for (i = 1; i <= N; i++) if (dep[mx] < dep[i]) mx = i;
ll md = dep[mx];
int v = mx;
rt = mx;
while (v) {
if (max(dep[v], dep[mx] - dep[v]) < md) {
md = max(dep[v], dep[mx] - dep[v]);
rt = v;
}
v = prt[v];
}
dfs(rt);
make_range(rt);
segtree::init(1, N);
ll sum = 0;
for (i = 1; i <= K; i++) {
auto [d, v] = segtree::query(1, N, 1, N);
v = rev[v];
sum += d;
while (v) {
if (vis[v]) break;
vis[v] = 1;
segtree::upd(1, N, range[v].first, range[v].second, -up[v]);
v = prt[v];
}
}
for (i = 1; i <= N; i++) getdis(i);
for (i = 1; i <= N; i++) if (adj[i].size() > 1 || !vis[i]) ans[i] = sum + dis[i];
auto [d, _] = segtree::query(1, N, 1, N);
sum += d;
for (i = 1; i <= N; i++) if (adj[i].size() == 1 && vis[i]) ans[i] = sum;
for (i = 1; i <= N; i++) cout << ans[i] << ln;
}
Compilation message
Main.cpp: In function 'void segtree::init(int, int, int)':
Main.cpp:101:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
101 | int m = s + e >> 1;
| ~~^~~
Main.cpp: In function 'void segtree::upd(int, int, int, int, ll, int)':
Main.cpp:122:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | int m = s + e >> 1;
| ~~^~~
Main.cpp: In function 'pli segtree::query(int, int, int, int, int)':
Main.cpp:131:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
131 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
13100 KB |
Output is correct |
| 2 |
Correct |
113 ms |
15276 KB |
Output is correct |
| 3 |
Correct |
81 ms |
13132 KB |
Output is correct |
| 4 |
Correct |
93 ms |
13120 KB |
Output is correct |
| 5 |
Correct |
92 ms |
14120 KB |
Output is correct |
| 6 |
Correct |
77 ms |
13228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
