Submission #1262382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262382		EntityPlantt	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	5094 ms	8296 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});
	}
	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';
	}
}

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