Submission #1263625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263625		OgradL	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	1223 ms	128576 KiB

diameter

#include <array>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int n, q;
long long W;

struct segtree{

	int N, height;
	vector<long long> tree, lazy;

	segtree() {}

	segtree(int sz){
		N = sz;
		height = 32 - __builtin_clz(N);
		tree.assign(2 * N, 0);
		lazy.assign(N, 0);
	}

	void build_all(vector<long long>& v){
		for (int i = 0; i < v.size(); i++){
			tree[N + i] = v[i];
		}
		for (int i = N - 1; i > 0; --i) tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}

	void apply(int p, long long value) {
		tree[p] += value;
		if (p < N) lazy[p] += value;
	}

	void build(int p) {
		while (p > 1) p >>= 1, tree[p] = max(tree[p<<1], tree[p<<1|1]) + lazy[p];
	}

	void push(int p) {
		for (int s = height; s > 0; --s) {
			int i = p >> s;
			if (lazy[i] != 0) {
				apply(i<<1, lazy[i]);
				apply(i<<1|1, lazy[i]);
				lazy[i] = 0;
			}
		}
	}

	void update(int l, int r, long long value) {
		l += N, r += N;
		int l0 = l, r0 = r;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l&1) apply(l++, value);
			if (r&1) apply(--r, value);
		}
		build(l0);
		build(r0 - 1);
	}

	int query(int l, int r) {
		l += N, r += N;
		push(l);
		push(r - 1);
		long long res = 0;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l&1) res = max(res, tree[l++]);
			if (r&1) res = max(tree[--r], res);
		}
		return res;
	}
};

int root;
vector<vector<pair<int, long long>>> adj;
vector<vector<array<int, 3>>> ancestors;
vector<array<long long, 3>> edges;
vector<int> subtree_sz, removed;

vector<segtree> segtrees;
vector<vector<int>> tins, touts;
vector<vector<long long>> tours;
vector<int> timers;

vector<multiset<long long>> max_dists;
multiset<long long> max_diams;

int find_subtree_sz(int v, int p = 0){
	subtree_sz[v] = 1;
	for (auto [x, w] : adj[v]){
		if (x != p && !removed[x])
			subtree_sz[v] += find_subtree_sz(x, v);
	}
	return subtree_sz[v];
}

int find_centroid(int v, int sz, int p = 0){
	for (auto [x, w] : adj[v]){
		if (x == p || removed[x]) continue;
		if (subtree_sz[x] * 2 >= sz)
			return find_centroid(x, sz, v);
	}
	return v;
}

void assign_ancestors(int v, int p, int level, int child_idx, int centroid, int d, long long total_w){
	tins[level][v] = timers[level]++;
	tours[level][tins[level][v]] = total_w;
	ancestors[v].push_back({centroid, d, child_idx});
	for (auto [x, w] : adj[v]){
		if (removed[x] || x == p) continue;
		assign_ancestors(x, v, level, child_idx, centroid, d + 1, total_w + w);
	}
	touts[level][v] = timers[level];
}

long long get_max_diam(int k){
	long long res = 0;
	auto it = max_dists[k].rbegin();
	res += *it;
	res += *next(it);
	return res;
}

int build_centroid(int v, int level = 0, int build_ms = 0){
	find_subtree_sz(v);
	int centroid = find_centroid(v, subtree_sz[v]);

	removed[centroid] = 1;
	if (!build_ms){
		ancestors[centroid].push_back({centroid, 0, -1});
	} else {
		max_dists[centroid].insert(0);
		max_dists[centroid].insert(0);
	}

	for (auto [x, w] : adj[centroid]){
		if (removed[x]) continue;
		if (!build_ms){
			assign_ancestors(x, centroid, level, x, centroid, 1, w);
		} else {
			long long diam = segtrees[level].query(tins[level][x], touts[level][x]);
			max_dists[centroid].insert(diam);
		}
		int c = build_centroid(x, level + 1, build_ms);
	}

	if (build_ms){
		max_diams.insert(get_max_diam(centroid));
	}

	return centroid;
}

void update_multiset(multiset<long long>& mset, long long pre, long long nxt){
	auto it = mset.find(pre);
	mset.erase(it);

	mset.insert(nxt);
}

void update(int k, long long e){
	auto& [a, b, w] = edges[k];

	long long diff = e - w;

	int min_sz = min(ancestors[a].size(), ancestors[b].size());

	for (int i = 0; i < min_sz; i++){
		if (ancestors[a][i][1] < ancestors[b][i][1]){
			swap(a, b);
		}

		auto [centroid, dist, idx_child] = ancestors[a][i];
		
		// increase a subtree distances by diff
		long long pre_max = segtrees[i].query(tins[i][idx_child], touts[i][idx_child]);

		segtrees[i].update(tins[i][a], touts[i][a], diff);

		long long nxt_max = segtrees[i].query(tins[i][idx_child], touts[i][idx_child]);

		if (pre_max == nxt_max)
			continue;

		// update max_dist[centroid]
		long long pre_diam = get_max_diam(centroid);

		update_multiset(max_dists[centroid], pre_max, nxt_max);

		long long nxt_diam = get_max_diam(centroid);

		if (pre_diam == nxt_diam)
			continue;

		// update max_diams
		update_multiset(max_diams, pre_diam, nxt_diam);
	}

	w = e;
}

long long get_answer(){
	return *max_diams.rbegin();
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q >> W;

	adj.resize(n);
	
	long long a, b, c;
	for (int i = 0; i < n-1; i++){
		cin >> a >> b >> c;
		--a, --b;

		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
		edges.push_back({a, b, c});
	}

	removed.assign(n, 0);
	subtree_sz.assign(n, -1);
	ancestors.resize(n);

	segtrees.assign(18, segtree(n));
	tins.assign(18, vector<int>(n));
	touts.assign(18, vector<int>(n));
	tours.assign(18, vector<long long>(n));
	timers.assign(18, 0);

	max_dists.resize(n);

	root = build_centroid(0);

	for (int i = 0; i < 18; i++){
		segtrees[i].build_all(tours[i]);
	}

	removed.assign(n, 0);
	build_centroid(0, 0, 1);

	long long last = 0;
	long long d, e;

	while (q--){
		cin >> d >> e;

		d = (d + last) % (n - 1);
		e = (e + last) % W;

		update(d, e);

		last = get_answer();

		cout << last << "\n";
	}

	return 0;
}

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