Submission #856238

#	Time	Username	Problem	Language	Result	Execution time	Memory
856238		mbfibat	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	228 ms	83404 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e5 + 11;

typedef pair<int, int> ii;

int n, q, w;
int a[N];
int cost[N];
ii E[N];
vector<int> adj[N], pos[N];

int top = 0;
void dfs(int u, int id_edge, int p = 0) {
	for (int id : adj[u]) {
		int x = E[id].first, y = E[id].second;
		if (x == u) swap(x, y);
		if (x == p) continue;

		a[++top] = cost[id];
		pos[id].push_back(top);
		dfs(x, id, u);
	}
	if (p) {
		a[++top] = -cost[id_edge];
		pos[id_edge].push_back(top);
	}
}

struct Node {
	int pfix, sfix; // pfix get maximum prefix sum, sfix get maximum -suffix sum
	int ans_pre, ans_suf; // f but ans_pre touch left, ans_suf touch right
	int all; // f but touch left and touch right
	int sum, f;
	Node(){}
};

Node Seg[4 * N];

void merge(int node) {	
	Seg[node].pfix = max(Seg[node * 2].pfix, Seg[node * 2].sum + Seg[node * 2 + 1].pfix);
	Seg[node].sfix = max(Seg[node * 2 + 1].sfix, -Seg[node * 2 + 1].sum + Seg[node * 2].sfix);

	Seg[node].sum = Seg[node * 2].sum + Seg[node * 2 + 1].sum;

	Seg[node].all = max(Seg[node * 2].all + Seg[node * 2 + 1].sum, -Seg[node * 2].sum + Seg[node * 2 + 1].all);

	Seg[node].ans_pre = max(max(Seg[node * 2].ans_pre, Seg[node * 2].all + Seg[node * 2 + 1].pfix), -Seg[node * 2].sum + Seg[node * 2 + 1].ans_pre);
	Seg[node].ans_suf = max(max(Seg[node * 2 + 1].ans_suf, Seg[node * 2 + 1].all + Seg[node * 2].sfix), Seg[node * 2 + 1].sum + Seg[node * 2].ans_suf);

	Seg[node].f = max(Seg[node * 2].f, Seg[node * 2 + 1].f);
	Seg[node].f = max(Seg[node].f, Seg[node * 2].ans_suf + Seg[node * 2 + 1].pfix);
	Seg[node].f = max(Seg[node].f, Seg[node * 2].sfix + Seg[node * 2 + 1].ans_pre);
}

void build(int node, int l, int r) {
	if (l == r) {
		Seg[node].pfix = max(0LL, a[l]); Seg[node].sfix = max(0LL, -a[l]);
		Seg[node].f = Seg[node].ans_pre = Seg[node].ans_suf = Seg[node].all = abs(a[l]);
		Seg[node].sum = a[l];
		return;		
	}

	int mi = (l + r) / 2;
	build(node * 2, l, mi);
	build(node * 2 + 1, mi + 1, r);

	merge(node);
}

void upd(int node, int l, int r, int pos) {
	if (l == r) {
		Seg[node].pfix = max(0LL, a[l]); Seg[node].sfix = max(0LL, -a[l]);
		Seg[node].f = Seg[node].ans_pre = Seg[node].ans_suf = Seg[node].all = abs(a[l]);
		Seg[node].sum = a[l];
		return;		
	}

	int mi = (l + r) / 2;
	if (pos <= mi) upd(node * 2, l, mi, pos);
	else upd(node * 2 + 1, mi + 1, r, pos);

	merge(node);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> q >> w;
	for (int i = 0; i < n - 1; i++) {
		int u, v; 
		cin >> u >> v >> cost[i];
		E[i] = ii(u, v);

		adj[u].emplace_back(i);		
		adj[v].emplace_back(i);		
	}
	dfs(1, -1);

	build(1, 1, 2 * (n - 1));

	int last = 0;
	while (q--) {
		int d, e; cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;		

  		a[pos[d][0]] = e;
  		upd(1, 1, 2 * (n - 1), pos[d][0]);
  		a[pos[d][1]] = -e;
  		upd(1, 1, 2 * (n - 1), pos[d][1]);

  		last = Seg[1].f;
		cout << last << '\n';
	}
}

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