Submission #594575

#	Time	Username	Problem	Language	Result	Execution time	Memory
594575		penguinhacker	Dynamic Diameter (CEOI19_diameter)	C++17	11 / 100	5094 ms	11896 KiB

diameter

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, eu[mxN], ev[mxN];
ll wlim, ew[mxN];
vector<int> adj[mxN];
vector<ll> st;

void dfs(int u=0, int p=-1, ll d=0) {
	st.push_back(d);
	for (int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if (v!=p) {
			dfs(v, u, d+ew[e]);
			st.push_back(d);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> wlim;
	for (int i=0; i<n-1; ++i) {
		cin >> eu[i] >> ev[i] >> ew[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	ll ans=0;
	while(q--) {
		int i;
		ll nxt;
		cin >> i >> nxt;
		i=(i+ans)%(n-1);
		nxt=(nxt+ans)%wlim;
		ew[i]=nxt;

		st.clear();
		dfs();
		assert(st.size()==2*n-1);

		ans=0;
		for (int i=0; i<2*n-1; ++i) {
			ll mn=3e18;
			for (int j=i; j<2*n-1; ++j) {
				mn=min(mn, st[j]);
				ans=max(ans, st[i]+st[j]-2*mn);
			}
			//cout << st[i] << " ";
		}
		//cout << endl;

		cout << ans << "\n";
	}
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from diameter.cpp:1:
diameter.cpp: In function 'int main()':
diameter.cpp:44:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   assert(st.size()==2*n-1);
      |          ~~~~~~~~~^~~~~~~

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