Submission #618879

#	Time	Username	Problem	Language	Result	Execution time	Memory
618879		Drew_	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5086 ms	4288 KiB

diameter

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

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;
using ll = long long;

const int MAX = 5069;

int N, Q, W;
int len[MAX];
vector<ii> adj[MAX];

ll depth[MAX];

inline ll getdia()
{
	const auto dfs = [&](const auto &self, int node, int par) -> void
	{	
		for (auto [to, id] : adj[node]) if (to != par)
		{
			depth[to] = depth[node] + len[id];
			self(self, to, node);
		}
	};
	depth[1] = 0;
	dfs(dfs, 1, -1);

	int best = 1;
	for (int i = 2; i <= N; ++i)
		if (depth[best] < depth[i])
			best = i;

	depth[best] = 0;
	dfs(dfs, best, -1);
	return *max_element(depth+1, depth+N+1);
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> Q >> W;
	for (int i = 0, u, v; i < N-1; ++i)
	{
		cin >> u >> v >> len[i];
		adj[u].pb({v, i});
		adj[v].pb({u, i});
	}

	for (int prv = 0, i, x; Q--;)
	{
		cin >> i >> x;
		(i += prv) %= (N-1);
		(x += prv) %= W;

		// cerr << i << " and " << x << '\n';

		len[i] = x;
		cout << (prv = getdia()) << '\n';
	}

	return 0;
}

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