Submission #855172

#	Time	Username	Problem	Language	Result	Execution time	Memory
855172		mbfibat	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4668 ms	347628 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);
	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);
	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;
unordered_map<int, int> st[N], ed[N];
 
multiset<int> val_ms[N];
vector<ii> val_ord[N];
 
void dfs(int u, int d = 0, int p = 0) {
	st[cur_root][u] = ++top[cur_root];
	dist[top[cur_root]] = d;
 
	for (auto [v, w] : adj[u]) {
		if (is_c[v] || v == p) continue;
		dfs(v, d + w, u);
	}
	ed[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
 
	// 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[root][v], r = ed[root][v];
		int val = query(Seg[root], 1, top[root], l, r);
 
		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_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;

	if (nChild[c] >= 2)
		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) {
	int u = ((st[root][u1] > st[root][u2]) ? u1 : u2);
	upd(Seg[root], 1, top[root], st[root][u], ed[root][u], inc);
                                                      
	int p = upper_bound(val_ord[root].begin(), val_ord[root].end(), ii(st[root][u], 2e18)) - val_ord[root].begin() - 1;
	int l = val_ord[root][p].first, r = val_ord[root][p + 1].first - 1;
 
	int old_val = val_ord[root][p].second;
	int new_val = query(Seg[root], 1, top[root], l, r); 
 
	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;
 
	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);

//	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

	int last = 0;
	while (q--) {
//		if (q % 1000 == 0) cerr << q << '\n';
		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);
 
		upd_edge(u, u, v, dif);
 
		last = *ans.rbegin();
		cout << last << '\n';
	}
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\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