Submission #672955

#	Time	Username	Problem	Language	Result	Execution time	Memory
672955		pavement	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	392 ms	63572 KiB

diameter

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int n, q, w, idx, a[100005], b[100005], c[100005], dep[100005], st[100005], ed[100005], seq[200005];
vector<ii> adj[100005];

void dfs(int n, int e = -1) {
	idx++;
	seq[idx] = n;
	st[n] = ed[n] = idx;
	for (auto [u, w] : adj[n]) if (u != e) {
		dep[u] = dep[n] + w;
		dfs(u, n);
		idx++;
		seq[idx] = n;
		ed[n] = idx;
	}
}

struct node {
	node *left, *right;
	int S, E, pv, val[6];
	void combine() {
		for (int k = 0; k < 6; k++)
			val[k] = max(left->val[k], right->val[k]);
		val[3] = max(val[3], left->val[0] + right->val[1]);
		val[4] = max(val[4], left->val[1] + right->val[2]);
		val[5] = max({val[5], left->val[3] + right->val[2], left->val[0] + right->val[4]});
	}
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val[0] = val[2] = dep[seq[S]];
			val[1] = -2 * dep[seq[S]];
			val[3] = val[4] = -dep[seq[S]];
			val[5] = 0;
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		combine();
	}
	void prop() {
		if (S == E || !pv) return;
		for (auto i : {left, right}) {
			for (int k = 0; k < 5; k++)
				if (k == 0 || k == 2) i->val[k] += pv;
				else if (k == 1) i->val[k] -= 2 * pv;
				else if (k == 3 || k == 4) i->val[k] -= pv;
			i->pv += pv;
		}
		pv = 0;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			for (int k = 0; k < 5; k++)
				if (k == 0 || k == 2) val[k] += v;
				else if (k == 1) val[k] -= 2 * v;
				else if (k == 3 || k == 4) val[k] -= v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		combine();
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> w;
	for (int i = 1; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].eb(b[i], c[i]);
		adj[b[i]].eb(a[i], c[i]);
	}
	dfs(1);
	for (int i = 1; i < n; i++) {
		if (dep[a[i]] > dep[b[i]]) swap(a[i], b[i]);
	}
	root = new node(1, idx);
	for (int d, e, last = 0; q--; ) {
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		d++;
		root->upd(st[b[d]], ed[b[d]], e - c[d]);
		c[d] = e;
		cout << (last = root->val[5]) << '\n';
	}
}

Compilation message (stderr)

diameter.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main() {
      | ^~~~

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