Submission #855164

#	Time	Username	Problem	Language	Result	Execution time	Memory
855164		mbfibat	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5050 ms	376364 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef pair<int, int> ii;

const int N = 1e5 + 11;

vector<ii> adj[N];

bool is_c[N];

int totChild = 0;
int nChild[N];
int parCentroid[N];
void cal_child(int u, int p = 0) {
	nChild[u] = 1;
	for (auto [v, w] : adj[u])
		if (!is_c[v] && v != p) {
			cal_child(v, u);
			nChild[u] += nChild[v];
		}	
}
int find_c(int u, int p = 0) {
	for (auto [v, w] : adj[u])
		if (v != p && !is_c[v] && nChild[v] > totChild / 2)
			return find_c(v, u);
	return u;	
}

// --------------------------------------------

unordered_map<int, int> dist;

struct Node {
	int val = 0, lazy = 0;
	Node* l = nullptr, *r = nullptr;
	Node(){}
};

// each centroid root will have a segtree
Node* Seg[N];

void build(Node *cur, int l, int r) {
	if (l == r) {
		cur -> val = dist[l];
		return;
	}
	cur -> l = new Node();
	cur -> r = new Node();
	int mi = (l + r) / 2;
	build(cur -> l, l, mi);
	build(cur -> r, mi + 1, r);
	cur -> val = max(cur -> l -> val, cur -> r -> val);
}

void diffuse(Node *cur, int l, int r) {
	if (cur -> lazy) {
		cur -> val += cur -> lazy;
		if (l != r) {
			cur -> l -> lazy += cur -> lazy;
			cur -> r -> lazy += cur -> lazy;
		}
		cur -> lazy = 0;
	}
}

void upd(Node *cur, int l, int r, int L, int R, int val) {
	diffuse(cur, l, r);
//	cerr << "UPDATE: " << l << ' ' << r << ' ' << cur -> val << '\n';
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		cur -> lazy += val;
		diffuse(cur, l, r);
		return;
	}

	int mi = (l + r) / 2;
	upd(cur -> l, l, mi, L, R, val);
	upd(cur -> r, mi + 1, r, L, R, val);
	cur -> val = max(cur -> l -> val, cur -> r -> val);
}

int query(Node *cur, int l, int r, int L, int R) {
	diffuse(cur, l, r);
//	cerr << "QUERY: " << l << ' ' << r << ' ' << cur -> val << '\n';
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return cur -> val;

	int mi = (l + r) / 2;
	int val_l = query(cur -> l, l, mi, L, R);
	int val_r = query(cur -> r, mi + 1, r, L, R);
	return max(val_l, val_r);
}

int cur_root;
unordered_map<int, int> top;
map<ii, int> st, ed;

multiset<int> val_ms[N];
vector<ii> val_ord[N];

void dfs(int u, int d = 0, int p = 0) {
	st[ii(cur_root, u)] = ++top[cur_root];
	dist[top[cur_root]] = d;

//	cerr << "dist from cur_root to u: " << cur_root << ' ' << u << ' ' << d << " - with pos: " << top[cur_root] << '\n';

	for (auto [v, w] : adj[u]) {
		if (is_c[v] || v == p) continue;
		dfs(v, d + w, u);
	}
	ed[ii(cur_root, u)] = top[cur_root];
}

// get max of all paths throught u
int sol[N];
multiset<int> ans;

void prep(int root) {
	// for each centroid root, create a segment tree, using pointers to create this egment tree
	// store a multiset for each edge from root
	// using st[u] and ed[u] to get the range and know, when updating a subtree, we know what edge from root does that subtree belong

//	cerr << "root: " << root << '\n';

	// 1. create segtree: get all nodes that are !is_c[u]
	cur_root = root;

	Seg[root] = new Node();
	dist[root] = 0;
	dfs(root);
	build(Seg[root], 1, top[root]);


	// 2. store multiset for each edge
	for (auto [v, w] : adj[root]) {
		if (is_c[v]) continue;

		int l = st[ii(root, v)], r = ed[ii(root, v)];
		int val = query(Seg[root], 1, top[root], l, r);
//		cerr << "range get and query: " << l << ' ' << r << ' ' << val << '\n';

		val_ms[root].insert(val);
		val_ord[root].emplace_back(l, val);
	}
	sort(val_ord[root].begin(), val_ord[root].end());

	// offset for easier handling
	val_ms[root].insert(0); val_ms[root].insert(0);
	val_ord[root].emplace_back(top[root] + 1, 0);

	auto it = val_ms[root].rbegin();
	int v1 = *it; ++it; int v2 = *it;
	sol[root] = v1 + v2; ans.insert(sol[root]);
}

// --------------------------------------------

void centroid_decompose(int u, int p = 0) {
	cal_child(u); totChild = nChild[u];
	int c = find_c(u);

	parCentroid[c] = p;
	prep(c);

	is_c[c] = true;
	for (auto [v, w] : adj[c])
		if (!is_c[v])
			centroid_decompose(v, c);
}

void upd_edge(int root, int u1, int u2, int inc) {
//	cerr << '?' << root << ' ' << u1 << ' ' << u2 << ' ' << inc << '\n';
	// update on tree
//	for (auto [pos, v] : val_ord[root]) {
//		cerr << pos << ' ' << v << '\n';
//	}	
	int u = ((st[ii(root, u1)] > st[ii(root, u2)]) ? u1 : u2);
	upd(Seg[root], 1, top[root], st[ii(root, u)], ed[ii(root, u)], inc);
//	cerr << "range of subtree: " << st[ii(root, u)] << " " << ed[ii(root, u)] << '\n';

	int p = upper_bound(val_ord[root].begin(), val_ord[root].end(), ii(st[ii(root, u)], 2e18)) - val_ord[root].begin() - 1;
	int l = val_ord[root][p].first, r = val_ord[root][p + 1].first - 1;
//	cerr << "range of root edge: " << l << " " << r << '\n';

	int old_val = val_ord[root][p].second;
	int new_val = query(Seg[root], 1, top[root], l, r); 

//	cerr << "old val and new val: " << old_val << ' ' << new_val << '\n';
	val_ms[root].erase(val_ms[root].find(old_val));
	val_ms[root].insert(new_val);
	val_ord[root][p].second = new_val;

	auto it = val_ms[root].rbegin();
	int v1 = *it; ++it; int v2 = *it;
//	cerr << "two largest paths: " << v1 << ' ' << v2 << '\n';

	ans.erase(ans.find(sol[root]));
	sol[root] = v1 + v2; ans.insert(sol[root]);

	if (parCentroid[root])
		upd_edge(parCentroid[root], u1, u2, inc);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, q, w; cin >> n >> q >> w;

	vector<int> W(n);
	vector<ii> edges;
	for (int i = 0; i < n - 1; i++) {
		int u, v, c; cin >> u >> v >> c;

		W[i] = c;
		edges.emplace_back(u, v);

		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}
	centroid_decompose(1);

	int last = 0;
	while (q--) {
		int d, e; cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;		

		int dif = e - W[d]; W[d] = e;

		auto [u, v] = edges[d];
		if (top[u] < top[v]) swap(u, v);
//		cerr << "dif: " << dif << '\n';
//		cerr << "set new value: " << e << '\n';
//		cerr << "u, v and top[u], top[v]: " << u << ' ' << v << ' ' << top[u] << ' ' << top[v] << '\n';		

		upd_edge(u, u, v, dif);

//		cerr << "all best paths: ";
//		for (int v : ans)
//			cerr << v << ' ';
//		cerr << '\n';
			
		last = *ans.rbegin();
		cout << last << '\n';
	}

}

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