oj.uz

Submission #898902

# Submission time Handle Problem Language Result Execution time Memory
898902 2024-01-05T08:55:35 Z jinhan814 Dynamic Diameter (CEOI19_diameter) C++17
42 / 100
 756 ms 63388 KB 
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

using i64 = long long;

struct node {
	i64 w, h_mx, l_mx, l_smx, p_mx, dp, e;
	node() : node(0, 0, 0, 0, 0, 0, 1) {}
	explicit node(i64 w, i64 mx, i64 smx, i64 dp) :
		node(w, w, mx, smx, w + mx, max(w + mx, dp), 0) {}
	explicit node(i64 w, i64 h_mx, i64 l_mx, i64 l_smx, i64 p_mx, i64 dp, i64 e) :
		w(w), h_mx(h_mx), l_mx(l_mx), l_smx(l_smx), p_mx(p_mx), dp(dp), e(e) {}
};

ostream& operator<< (ostream& out, const node& x) {
	out << '(' << x.w << ' ' << x.h_mx << ' ' << x.l_mx << ' ' << x.l_smx << ' ' << x.p_mx << ' ' << x.dp << ' ' << x.e << ')';
	return out;
}

node merge(const node& a, const node& b) {
	if (a.e) return b;
	if (b.e) return a;
	node res{};
	res.w = b.w + a.w;
	res.h_mx = max(max(b.h_mx, b.l_mx) + a.w, a.h_mx);
	res.l_mx = a.l_mx;
	res.l_smx = a.l_smx;
	res.p_mx = max(b.p_mx, b.w + a.p_mx);
	res.dp = max({
		b.dp,
		a.dp,
		max(b.h_mx, b.l_mx) + a.p_mx,
		res.h_mx + res.l_mx,
		res.l_mx + res.l_smx });
	res.e = 0;
	return res;
}

struct segtree {
	segtree() : segtree(0) {}
	explicit segtree(int n) : sz(1 << __lg(n - 1) + 1), tree(sz << 1) {}
	void update(int i, const node& x) {
		tree[--i |= sz] = x;
		while (i >>= 1) tree[i] = merge(tree[i << 1], tree[i << 1 | 1]);
	}
	node query(int l, int r) const {
		node acc_l, acc_r;
		for (--l |= sz, --r |= sz; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) acc_l = merge(acc_l, tree[l++]);
			if (~r & 1) acc_r = merge(tree[r--], acc_r);
		}
		return merge(acc_l, acc_r);
	}
private:
	const int sz;
	vector<node> tree;
};

int main() {
	fastio;
	int n, q; cin >> n >> q;
	i64 w; cin >> w;
	vector e(n - 1, tuple(0, 0, 0LL));
	vector adj(n + 1, vector(0, 0));
	for (auto& [a, b, c] : e) {
		cin >> a >> b >> c;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	vector sz(n + 1, 1), dep(n + 1, 0), par(n + 1, 0);
	vector in(n + 1, 0), inv_in(n + 1, 0), top(n + 1, 0), bot(n + 1, 0);
	{
		auto dfs1 = [&](const auto& f, int cur, int prv) -> void {
			auto it = find(adj[cur].begin(), adj[cur].end(), prv);
			if (it != adj[cur].end()) adj[cur].erase(it);
			for (auto& nxt : adj[cur]) {
				dep[nxt] = dep[cur] + 1;
				par[nxt] = cur;
				f(f, nxt, cur);
				sz[cur] += sz[nxt];
				if (sz[adj[cur][0]] < sz[nxt]) swap(adj[cur][0], nxt);
			}
		};
		dfs1(dfs1, 1, 0);

		int ord = 0;
		auto dfs2 = [&](const auto& f, int cur) -> void {
			in[cur] = ++ord;
			inv_in[in[cur]] = cur;
			for (int nxt : adj[cur]) {
				top[nxt] = nxt == adj[cur][0] ? top[cur] : nxt;
				f(f, nxt);
			}
			bot[cur] = adj[cur].size() ? bot[adj[cur][0]] : cur;
		};
		dfs2(dfs2, top[1] = 1);
	}

	vector cost(n + 1, 0LL);
	for (auto& [a, b, c] : e) {
		if (par[a] == b) swap(a, b);
		cost[b] = c;
	}

	segtree tree(n);
	vector acc_dp(n + 1, multiset{ 0LL });
	vector acc_chain(n + 1, multiset{ 0LL, 0LL });

	auto get_mx = [](const auto& ms) { return *prev(ms.end()); };
	auto get_smx = [](const auto& ms) { return *prev(prev(ms.end())); };
	auto get_node = [&](int i) {
		if (adj[i].empty()) return node();
		int c = adj[i][0];
		return node(cost[c], get_mx(acc_chain[i]), get_smx(acc_chain[i]), get_mx(acc_dp[i]));
	};

	for (int _ = n; _ >= 1; _--) {
		int i = inv_in[_];
		tree.update(in[i], get_node(i));
		if (i == top[i]) {
			node res = tree.query(in[i], in[bot[i]]);
			acc_dp[par[i]].insert(res.dp);
			acc_chain[par[i]].insert(cost[i] + max(res.h_mx, res.l_mx));
		}
	}

	auto update = [&](int i, i64 c) {
		int cnt = 0;
		while (i) {
			{
				node res = tree.query(in[top[i]], in[bot[i]]);
				acc_dp[par[top[i]]].erase(acc_dp[par[top[i]]].find(res.dp));
				acc_chain[par[top[i]]].erase(acc_chain[par[top[i]]].find(cost[top[i]] + max(res.h_mx, res.l_mx)));
			}
			if (++cnt == 1) {
				cost[i] = c;
				if (i != top[i]) {
					int p = par[i];
					tree.update(in[p], get_node(p));
				}
			}
			tree.update(in[i], get_node(i));
			{
				node res = tree.query(in[top[i]], in[bot[i]]);
				acc_dp[par[top[i]]].insert(res.dp);
				acc_chain[par[top[i]]].insert(cost[top[i]] + max(res.h_mx, res.l_mx));
			}
			i = par[top[i]];
		}
		return get_mx(acc_dp[0]);
	};

	i64 res = 0;
	while (q--) {
		i64 i, c; cin >> i >> c;
		i = (i + res) % (n - 1);
		c = (c + res) % w;
		auto [a, b, _] = e[i];
		res = update(b, c);
		cout << res << '\n';
	}
}

Compilation message

diameter.cpp: In constructor 'segtree::segtree(int)':
diameter.cpp:42:48: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 |  explicit segtree(int n) : sz(1 << __lg(n - 1) + 1), tree(sz << 1) {}
      |                                    ~~~~~~~~~~~~^~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 984 KB Output is correct
2 Correct 14 ms 1104 KB Output is correct
3 Correct 86 ms 1588 KB Output is correct
4 Correct 134 ms 2320 KB Output is correct
5 Correct 11 ms 6232 KB Output is correct
6 Correct 34 ms 6492 KB Output is correct
7 Correct 131 ms 6960 KB Output is correct
8 Correct 213 ms 8148 KB Output is correct
9 Correct 44 ms 27728 KB Output is correct
10 Correct 72 ms 27728 KB Output is correct
11 Correct 178 ms 28496 KB Output is correct
12 Correct 318 ms 29340 KB Output is correct
13 Correct 90 ms 54940 KB Output is correct
14 Correct 120 ms 55124 KB Output is correct
15 Correct 248 ms 55924 KB Output is correct
16 Correct 406 ms 56716 KB Output is correct
17 Correct 756 ms 56404 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 58368 KB Output is correct
2 Correct 678 ms 58428 KB Output is correct
3 Correct 702 ms 58452 KB Output is correct
4 Correct 625 ms 58388 KB Output is correct
5 Correct 672 ms 58968 KB Output is correct
6 Correct 651 ms 61344 KB Output is correct
7 Correct 410 ms 60496 KB Output is correct
8 Correct 448 ms 60384 KB Output is correct
9 Correct 427 ms 60400 KB Output is correct
10 Correct 415 ms 60544 KB Output is correct
11 Correct 409 ms 60884 KB Output is correct
12 Correct 367 ms 62924 KB Output is correct
13 Correct 363 ms 62268 KB Output is correct
14 Correct 343 ms 62236 KB Output is correct
15 Correct 336 ms 62288 KB Output is correct
16 Correct 319 ms 62228 KB Output is correct
17 Correct 337 ms 62520 KB Output is correct
18 Correct 297 ms 63388 KB Output is correct
19 Correct 352 ms 62172 KB Output is correct
20 Correct 325 ms 62156 KB Output is correct
21 Correct 335 ms 62464 KB Output is correct
22 Correct 312 ms 62292 KB Output is correct
23 Correct 366 ms 62372 KB Output is correct
24 Correct 296 ms 63320 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -