Submission #359302

#	Time	Username	Problem	Language	Result	Execution time	Memory
359302		jesus_coconut	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5072 ms	15316 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, q;
ll w;
vector<map<int, int>> adj;
vector<pair<int, int>> edges;
bool s3 = true;

void read() {
	cin >> n >> q >> w;
	adj.resize(n);
	edges.resize(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		ll c;
		cin >> a >> b >> c;
		--a; --b;
		if (a != 0) s3 = false;
		edges[i] = {a, b};
		adj[a][b] = c;
		adj[b][a] = c;
	}
}

void solve3() {
	vector<multiset<ll>::iterator> v(n - 1);
	multiset<ll, greater<>> s;
	for (int i = 0; i < n - 1; ++i) {
		v[i] = s.insert(adj[edges[i].first][edges[i].second]);
	}
	ll last = 0;
	while (q--) {
		int dd;
		ll ee;
		cin >> dd >> ee;
		int d = ((ll)dd + last) % (n - 1);
		ll e = (ee + last) % w;
		adj[edges[d].first][edges[d].second] = e;
		adj[edges[d].second][edges[d].first] = e;
		s.erase(v[d]);
		v[d] = s.insert(e);
		last = *s.begin() + *(++s.begin());
		cout << last << '\n';
	}
}

ll mxcost;
int far;

void dfs(int ver, int par, ll cost) {
	if (cost > mxcost) {
		mxcost = cost;
		far = ver;
	}
	for (auto &[u, c] : adj[ver]) if (u != par) {
		dfs(u, ver, cost + c);
	}
}

ll diameter() {
	mxcost = 0;
	far = 0;
	dfs(0, -1, 0);
	mxcost = 0;
	dfs(far, -1, 0);
	return mxcost;
}

void solve() {
	ll last = 0;
	while (q--) {
		int dd;
		ll ee;
		cin >> dd >> ee;
		int d = ((ll)dd + last) % (n - 1);
		ll e = (ee + last) % w;
		adj[edges[d].first][edges[d].second] = e;
		adj[edges[d].second][edges[d].first] = e;
		last = diameter();
		cout << last << '\n';
	}
}

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

	read();
	if (s3) {
		solve3();
	} else {
		solve();
	}

	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