Submission #1263485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263485		OgradL	Dynamic Diameter (CEOI19_diameter)	C++20	11 / 100	5094 ms	8184 KiB

diameter

#include <array>
#include <iostream>
#include <vector>
using namespace std;

int n, q;
long long W;

vector<array<long long, 3>> edges;
vector<vector<int>> adj;

void update(int k, long long e){
	auto& [a, b, w] = edges[k];

	w = e;
}

long long get_answer(){
	long long ans = 0;

	for (int i = 0; i < n; i++){
		auto dfs = [&](auto&& dfs, int v, int p, long long d) -> void {
			ans = max(ans, d);
			for (int idx : adj[v]){
				auto [a, b, w] = edges[idx];
				int x = a + b - v;
				if (x != p)
					dfs(dfs, x, v, d + w);
			}
		};

		dfs(dfs, i, -1, 0);
	}

	return ans;
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> q >> W;

	adj.resize(n);
	
	long long a, b, c;
	for (int i = 0; i < n-1; i++){
		cin >> a >> b >> c;
		--a, --b;

		adj[a].push_back(i);
		adj[b].push_back(i);
		edges.push_back({a, b, c});
	}

	long long last = 0;
	long long d, e;

	while (q--){
		cin >> d >> e;

		d = (d + last) % (n - 1);
		e = (e + last) % W;

		update(d, e);

		last = get_answer();

		cout << last << "\n";
	}

	return 0;
}

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