Submission #898902

#	Time	Username	Problem	Language	Result	Execution time	Memory
898902		jinhan814	Dynamic Diameter (CEOI19_diameter)	C++17	42 / 100	756 ms	63388 KiB

diameter

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

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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 27