Submission #676178

#	Time	Username	Problem	Language	Result	Execution time	Memory
676178		vovamr	Paths (RMI21_paths)	C++17	100 / 100	479 ms	54088 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 1e5 + 10;
const int lg = 17;

int n, k;
ve<pii> gr[N];

int up[N][lg];
ll d[N], act[N];

int mx[N], mxu[N];

struct Node {
	Node *l = nullptr;
	Node *r = nullptr;
	ll s = 0;
	int sz; ll k, p;
	Node(ll x) : k(x), s(x), sz(1) { p = rng() % inf; }
};
typedef Node* nd;
inline int sz(nd t) { return !t ? 0 : t->sz; }
inline ll s(nd t) { return !t ? 0 : t->s; }
inline void upd(nd t) {
	if (!t) return;
	t->sz = sz(t->l) + 1 + sz(t->r);
	t->s = s(t->l) + t->k + s(t->r);
}
inline nd mg(nd a, nd b) {
	if (!a || !b) return !a ? b : a;
	if (a->p > b->p) { a->r = mg(a->r, b); upd(a); return a; }
	else { b->l = mg(a, b->l); upd(b); return b; }
}
inline pair<nd,nd> sp(nd t, ll s) {
	if (!t) return {nullptr, nullptr};
	int q = sz(t->r);
	if (s > q) { auto tt = sp(t->l, s - q - 1); t->l = tt.se; upd(t); return {tt.fi, t}; }
	else { auto tt = sp(t->r, s); t->r = tt.fi; upd(t); return {t, tt.se}; }
}
inline pair<nd,nd> spk(nd t, ll x) {
	if (!t) return {nullptr, nullptr};
	if (t->k <= x) { auto tt = spk(t->r, x); t->r = tt.fi; upd(t); return {t, tt.se}; }
	else { auto tt = spk(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline void ins(nd &t, ll x) {
	auto [t1, t2] = spk(t, x);
	t = mg(t1, mg(new Node(x), t2));
}
inline void del(nd &t, ll x) {
	auto [t1, t2] = spk(t, x - 1);
	int S = sz(t2);
	auto [t3, t4] = sp(t2, sz(t2) - 1);
	assert(sz(t3) == 1);
	assert(s(t3) == x);
	assert(sz(t4) == S - 1);
	t = mg(t1, t4);
}

nd rt = nullptr;

inline void add(const ll &x) {
	ins(rt, x);
}
inline void del(const ll &x) {
	del(rt, x);
}
inline ll get() {
	auto [t1, t2] = sp(rt, k);
	ll res = s(t2);
	rt = mg(t1, t2);
	return res;
}

inline void dfs(int v, int p) {
	if (v == p) d[v] = 0;

	up[v][0] = p;
	for (int i = 1; i < lg; ++i) up[v][i] = up[up[v][i - 1]][i - 1];

	mx[v] = v;
	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		d[to] = d[v] + w;
		dfs(to, v);
		if (d[mx[to]] >= d[mx[v]]) mx[v] = mx[to];
	}
}
inline void dfs1(int v, int p) {
	if (gr[v].size() == 1) {
		int u = v;
		for (int i = lg - 1; ~i; --i) {
			if (mx[up[u][i]] == v) {
				u = up[u][i];
			}
		}
		act[v] = d[v] - d[up[u][0]];
	}
	else act[v] = 0;

	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		dfs1(to, v);
	}
}

pair<pll,pll> dpd[N];

inline void dfs2(int v, int p) {
	dpd[v] = {{0, v}, {0, v}};
	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		dfs2(to, v);

		chmax(dpd[v].se, mpp(dpd[to].fi.fi + w, dpd[to].fi.se));
		if (dpd[v].se > dpd[v].fi) swap(dpd[v].fi, dpd[v].se);
	}
}

pll dpu[N];
inline void dfs3(int v, int p, int pw) {
	if (v == p) dpu[v] = (gr[v].size() == 1 ? mpp(0, v) : mpp(-iinf, -iinf));
	else {
		chmax(dpu[v], mpp(dpu[p].fi + pw, dpu[p].se));

		if (dpd[p].fi.fi == dpd[v].fi.fi + pw) {
			chmax(dpu[v], mpp(dpd[p].se.fi + pw, dpd[p].se.se));
		}
		else {
			chmax(dpu[v], mpp(dpd[p].fi.fi + pw, dpd[p].fi.se));
		}
	}

	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;
		dfs3(to, v, w);
	}
}
inline void trans() {
	for (int i = 0; i < n; ++i) {
		mxu[i] = dpu[i].se;
	}
}

ll answer[N];

inline void dfs_reroot(int v, int p) {
	answer[v] = get();

	for (auto &[to, w] : gr[v]) {
		if (to == p) continue;

		del(act[mx[to]]);
		del(act[mxu[to]]);
		act[mx[to]] -= w;
		act[mxu[to]] += w;
		add(act[mx[to]]);
		add(act[mxu[to]]);

		dfs_reroot(to, v);

		del(act[mx[to]]);
		del(act[mxu[to]]);
		act[mxu[to]] -= w;
		act[mx[to]] += w;
		add(act[mx[to]]);
		add(act[mxu[to]]);
	}
}

inline void solve() {
	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		int v, u, c;
		cin >> v >> u >> c, --v, --u;
		gr[v].pb({u, c}), gr[u].pb({v, c});
	}

	int c = 0;
	for (int i = 0; i < n; ++i) {
		c += (gr[i].size() == 1);
	}
	chmin(k, c);

	int r = 0;

	dfs(r, r);
	dfs1(r, r);
	dfs2(r, r);
	dfs3(r, r, 0);
	trans();

/*
	for (int i = 0; i < n; ++i) {
		cout << "vertex: " << i + 1 << ":" << '\n';
		cout << "deepest: (" << dpd[i].fi.se + 1 << " = " << dpd[i].fi.fi << "), ";
		cout << "(" << dpd[i].se.se + 1 << " = " << dpd[i].se.fi << ")" << '\n';
		cout << "going up: (" << dpu[i].se + 1 << " = " << dpu[i].fi << ")" << '\n';
	}
*/

	for (int i = 0; i < n; ++i) {
		if (gr[i].size() == 1) {
			add(act[i]);
		}
	}

	dfs_reroot(r, r);

	for (int i = 0; i < n; ++i) cout << answer[i] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

Main.cpp: In constructor 'Node::Node(long long int)':
Main.cpp:37:13: warning: 'Node::k' will be initialized after [-Wreorder]
   37 |  int sz; ll k, p;
      |             ^
Main.cpp:36:5: warning:   'long long int Node::s' [-Wreorder]
   36 |  ll s = 0;
      |     ^
Main.cpp:38:2: warning:   when initialized here [-Wreorder]
   38 |  Node(ll x) : k(x), s(x), sz(1) { p = rng() % inf; }
      |  ^~~~

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