oj.uz

Submission #676169

# Submission time Handle Problem Language Result Execution time Memory
676169 2022-12-29T15:52:04 Z vovamr Paths (RMI21_paths) C++17
68 / 100
 526 ms 49892 KB 
#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 p, sz; ll k;
	Node(ll x) : k(x), s(x), sz(1) { p = rng() % iinf; }
};
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) {
	if (t->k == x) { t = mg(t->l, t->r); return; }
	if (x < t->k) del(t->l, x);
	else del(t->r, x);
	upd(t);
}

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] = {{-1, -1}, {-1, -1}};
	if (gr[v].size() == 1 && v != p) dpd[v].fi = {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] = {0, v};
	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});
	}

	dfs(0, 0);
	dfs1(0, 0);
	dfs2(0, 0);
	dfs3(0, 0, 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) {
		add(act[i]);
	}
	dfs_reroot(0, 0);

	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

Main.cpp: In constructor 'Node::Node(long long int)':
Main.cpp:37:16: warning: 'Node::k' will be initialized after [-Wreorder]
   37 |  int p, sz; ll k;
      |                ^
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() % iinf; }
      |  ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2812 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2812 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3156 KB Output is correct
10 Correct 4 ms 3156 KB Output is correct
11 Correct 4 ms 3076 KB Output is correct
12 Correct 4 ms 3080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2812 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3156 KB Output is correct
10 Correct 4 ms 3156 KB Output is correct
11 Correct 4 ms 3076 KB Output is correct
12 Correct 4 ms 3080 KB Output is correct
13 Correct 7 ms 3540 KB Output is correct
14 Correct 7 ms 3720 KB Output is correct
15 Correct 6 ms 3592 KB Output is correct
16 Correct 7 ms 3540 KB Output is correct
17 Correct 6 ms 3540 KB Output is correct
18 Correct 5 ms 3412 KB Output is correct
19 Correct 7 ms 3540 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 45712 KB Output is correct
2 Correct 454 ms 48272 KB Output is correct
3 Correct 355 ms 46028 KB Output is correct
4 Correct 526 ms 46328 KB Output is correct
5 Correct 445 ms 47232 KB Output is correct
6 Correct 471 ms 46268 KB Output is correct

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2812 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2812 KB Output is correct
8 Correct 4 ms 3176 KB Output is correct
9 Correct 4 ms 3156 KB Output is correct
10 Correct 4 ms 3156 KB Output is correct
11 Correct 4 ms 3076 KB Output is correct
12 Correct 4 ms 3080 KB Output is correct
13 Correct 7 ms 3540 KB Output is correct
14 Correct 7 ms 3720 KB Output is correct
15 Correct 6 ms 3592 KB Output is correct
16 Correct 7 ms 3540 KB Output is correct
17 Correct 6 ms 3540 KB Output is correct
18 Correct 5 ms 3412 KB Output is correct
19 Correct 7 ms 3540 KB Output is correct
20 Correct 519 ms 45712 KB Output is correct
21 Correct 454 ms 48272 KB Output is correct
22 Correct 355 ms 46028 KB Output is correct
23 Correct 526 ms 46328 KB Output is correct
24 Correct 445 ms 47232 KB Output is correct
25 Correct 471 ms 46268 KB Output is correct
26 Correct 502 ms 46708 KB Output is correct
27 Correct 474 ms 49420 KB Output is correct
28 Correct 432 ms 49892 KB Output is correct
29 Correct 341 ms 47304 KB Output is correct
30 Incorrect 502 ms 47912 KB Output isn't correct
31 Halted 0 ms 0 KB -