Submission #736248

#	Time	Username	Problem	Language	Result	Execution time	Memory
736248		flappybird	Paths (RMI21_paths)	C++17	12 / 100	113 ms	15276 KiB

Main

#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 (stderr)

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;
      |           ~~^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32