Submission #1262484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262484		EntityPlantt	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	1263 ms	14044 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, q;
	int64_t w, last = 0;
	cin >> n >> q >> w;
	vector<pair<int, int>> g[n];
	int edga[n - 1], edgb[n - 1];
	int64_t weight[n - 1];
	for (int i = 0; i < n - 1; i++) {
		cin >> edga[i] >> edgb[i] >> weight[i];
		g[--edga[i]].push_back({--edgb[i], i});
		g[edgb[i]].push_back({edga[i], i});
	}
	if (n < 5001) {
		const function<pair<int64_t, int>(int, int)> dfs = [&](int u, int p) {
			pair ans{0LL, u};
			for (auto &[v, e] : g[u]) {
				if (v == p) continue;
				pair p = dfs(v, u);
				ans = max(ans, {p.first + weight[e], p.second});
			}
			return ans;
		};
		while (q--) {
			int d;
			int64_t e;
			cin >> d >> e;
			weight[d = (d + last) % (n - 1)] = e = (e + last) % w;
			cout << (last = dfs(dfs(0, 0).second, -1).first) << '\n';
		}
		return 0;
	}
	multiset<int64_t> lens(weight, weight + n - 1);
	lens.insert(0);
	while (q--) {
		int d;
		int64_t e;
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		lens.erase(lens.find(weight[d]));
		lens.insert(weight[d] = e);
		cout << (last = *lens.rbegin() + *next(lens.rbegin())) << '\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