Submission #542791

#	Time	Username	Problem	Language	Result	Execution time	Memory
542791		blue	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5060 ms	2524 KiB

diameter

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

using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vi = vector<int>;

const int mx = 15'000;
const ll INF = 2'000'000'000'000'000'000LL;

int a[1+mx], b[1+mx];
ll l[1+mx];
vi edge[1+mx];

int n, q;
ll w;

vll getdistances(int src)
{
	vll res(1+n, INF);
	res[src] = 0;
	queue<int> tbv;
	tbv.push(src);
	while(!tbv.empty())
	{
		int u = tbv.front();
		tbv.pop();

		for(int e : edge[u])
		{
			int v = a[e] + b[e] - u;
			ll w = l[e];

			if(res[v] <= res[u] + w) continue;

			res[v] = res[u] + w;

			tbv.push(v);
		}
	}

	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;
	cin >> w;

	for(int e = 1; e <= n-1; e++)
	{
		cin >> a[e] >> b[e] >> l[e];
		edge[a[e]].push_back(e);
		edge[b[e]].push_back(e);
	}

	ll last = 0;

	for(int j = 1; j <= q; j++)
	{
		ll d, e;
		cin >> d >> e;

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

		l[d] = e;

		vll zd = getdistances(1);
		int mx = 1;
		for(int i = 2; i <= n; i++)
			if(zd[i] > zd[mx])
				mx = i;

		vll zd2 = getdistances(mx);
		last = 0;
		for(int i = 1; i <= n; i++)
			last = max(last, zd2[i]);

		cout << last << '\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