Submission #855118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855118	2023-09-30T07:48:29 Z	mbfibat	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	5000 ms	291952 KB

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;
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 u, int inc) {
//	cerr << '?' << root << ' ' << u << ' ' << inc << '\n';
	// update on tree
//	for (auto [pos, v] : val_ord[root]) {
//		cerr << pos << ' ' << v << '\n';
//	}	
	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], u, 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 << "u, v and top[u], top[v]: " << u << ' ' << v << ' ' << top[u] << ' ' << top[v] << '\n';		

		upd_edge(u, v, dif);

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

}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	12892 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	12892 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	12892 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12724 KB	Output is correct
4	Correct	11 ms	13148 KB	Output is correct
5	Correct	51 ms	14092 KB	Output is correct
6	Correct	2 ms	12888 KB	Output is correct
7	Correct	3 ms	13148 KB	Output is correct
8	Correct	3 ms	13148 KB	Output is correct
9	Correct	5 ms	13148 KB	Output is correct
10	Correct	18 ms	13400 KB	Output is correct
11	Correct	79 ms	14420 KB	Output is correct
12	Correct	11 ms	16728 KB	Output is correct
13	Correct	11 ms	16728 KB	Output is correct
14	Correct	14 ms	16792 KB	Output is correct
15	Correct	34 ms	16988 KB	Output is correct
16	Correct	132 ms	18260 KB	Output is correct
17	Correct	264 ms	92928 KB	Output is correct
18	Correct	264 ms	92716 KB	Output is correct
19	Correct	281 ms	92924 KB	Output is correct
20	Correct	316 ms	93112 KB	Output is correct
21	Correct	612 ms	94984 KB	Output is correct