Submission #917756

#	Time	Username	Problem	Language	Result	Execution time	Memory
917756		NK_	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	291 ms	54100 KiB

diameter

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
const ll INF = 7e18 + 10;

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

struct T {
	ll a, b, c, ab, bc, abc;

	T() { a = b = c = ab = bc = abc = -INF; }
	T(ll x) {
		a = x, b = -2 * x, c = x, ab = -x, bc = -x, abc = 0;
	}

	void upd(ll d) {
		a += d, b -= 2 * d, c += d, ab -= d, bc -= d;
	}

};

struct Seg {
	const T ID = T(); T comb(T a, T b) {
		T c = T(); 
		c.a = max(a.a, b.a), c.b = max(a.b, b.b), c.c = max(a.c, b.c);
		c.ab = max({a.ab, b.ab, a.a + b.b}), c.bc = max({a.bc, b.bc, a.b + b.c});
		c.abc = max({a.abc, b.abc, a.ab + b.c, a.a + b.bc});
		return c;
	};

	V<T> seg; vl lazy; int N; void init(int n) {
		for(N = 1; N < n; ) N *= 2;
		seg.assign(2 * N, ID); lazy.assign(2 * N, 0);
	}

	void push(int x, int L, int R) {
		seg[x].upd(lazy[x]);
		if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x];
		lazy[x] = 0;
	}

	void set(int p, T x) {
		seg[p += N] = x; for(p /= 2; p; p /= 2) pull(p);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void upd(int l, int r, ll v, int x, int L, int R) {
		push(x, L, R); if (r < L || R < l) return;
		if (l <= L && R <= r) {
			lazy[x] += v; push(x, L, R); return;
		}

		int M = (L + R) / 2;
		upd(l, r, v, 2 * x, L, M);
		upd(l, r, v, 2 * x + 1, M + 1, R);
		pull(x);
	}

	void upd(int l, int r, ll v) { upd(l, r, v, 1, 0, N - 1); }
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; ll MXW; cin >> N >> M >> MXW;

	V<vpi> adj(N); vi E(N - 1); vl W(N);

	for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v >> W[i]; --u, --v;
		adj[u].pb(mp(v, i));
		adj[v].pb(mp(u, i));
	}
	
	Seg S; S.init(2*N); vi st(N), en(N);

	vi ord; int t = 0; ll dep = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		st[u] = en[u] = t; S.set(t, T(dep)); ord.pb(u); t++;

		for(auto& e : adj[u]) {
			int v, i; tie(v, i) = e;
			if (v == p) continue;

			dep += W[i];
			E[i] = v; dfs(v, u);
			dep -= W[i];

			S.set(t, T(dep)); en[u] = t; ord.pb(u); t++; 
		}

	};

	dfs(0, -1);

	// for(int i = 0; i < N; i++) {
	// 	cout << i << " => " << st[i] << " " << en[i] << endl;
	// }

	// for(auto& x : ord) {
	// 	cout << x << " ";
	// }
	// cout << endl;

	// cout << S.seg[1].abc << endl;


	ll last = 0;
	for(int i = 0; i < M; i++) {
		ll e, w; cin >> e >> w;

		e = ll(e + last) % ll(N - 1);
		w = ll(w + last) % MXW;

		// cout << e << " " << w << endl;

		int u = E[e];
		S.upd(st[u], en[u], w - W[e]);
		W[e] = w;

		last = S.seg[1].abc;
		cout << last << nl;
	}

	exit(0-0);
}

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