Submission #556304

#	Time	Username	Problem	Language	Result	Execution time	Memory
556304		sidon	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	255 ms	52388 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
 
const int Z = 1e5, INF = 1e18+1;

int n, q, wLim, dfsTimer, e[Z*2], w[Z], sub[Z], L[Z], R[Z];
vector<pair<int, int>> g[Z];

void dfs(int u, int p, int d) {
	L[u] = dfsTimer;
	if(u && size(g[u]) < 2) e[L[u] = dfsTimer++] = d;

	for(auto [v, i] : g[u]) if(v != p) {
		dfs(sub[i] = v, u, d + w[i]);
		e[dfsTimer++] = d;
	}
	R[u] = dfsTimer-1;
}

int sL, sR, sV;
struct SegmentTree {
	int l, r, add {}; array<int, 5> v {};
	SegmentTree *L, *R;
	SegmentTree(int lv, int rv) : l(lv), r(rv) {
		if(r - l > 1) {
			int m = (l + r) / 2;
			L = new SegmentTree(l, m);
			R = new SegmentTree(m, r);
			pull();
		} else
			v = {e[l], -2 * e[l], -INF, -INF, -INF};
	}
	void pull() {
		v = {
			max(L->v[0], R->v[0]) + add,
			max(L->v[1], R->v[1]) - add * 2,
			max(max(L->v[2], R->v[2]), L->v[0] + R->v[1]) - add,
			max(max(L->v[3], R->v[3]), L->v[1] + R->v[0]) - add,
			max(max(L->v[4], R->v[4]), max(L->v[0] + R->v[3], L->v[2] + R->v[0]))
		};
	}
	void rangeAdd(int lv, int rv, int val) {
		sL = lv, sR = rv + 1, sV = val;
		rangeAdd();
	}
	void rangeAdd() {
		if(sL <= l && r <= sR) {
			add += sV;
			v[0] += sV;
			v[1] -= sV * 2;
			v[2] -= sV;
			v[3] -= sV;
			return;
		}
		if(sR <= l || r <= sL) return;
		L->rangeAdd();
		R->rangeAdd();
		pull();
	}
	int query() {
		return max(v[0], v[4]);
	}
};
 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> wLim;
 
	for(int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v >> w[i];
		--u, --v;
		g[u].emplace_back(v, i);
		g[v].emplace_back(u, i);
	}

	dfs(0, 0, 0);
	SegmentTree *st = new SegmentTree(0, dfsTimer);

	for(int last {}; q--; ) {
		int qD, qE; cin >> qD >> qE;
		(qD += last) %= n - 1;
		(qE += last) %= wLim;

		st->rangeAdd(L[sub[qD]], R[sub[qD]], qE - w[qD]);
		w[qD] = qE;

		cout << (last = st->query()) << '\n';
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27