Submission #1267202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267202		canhnam357	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	420 ms	67264 KiB

diameter

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
int lz[1 << 19] = {};
const int inf = 1e18;
struct info
{
	int a[3][3];
	info()
	{
		for (int i = 0; i < 3; i++) for (int j = i; j < 3; j++) a[i][j] = -inf;
	}
	info(int x)
	{
		// i <= j <= k
		// val[i] - 2 * val[j] + val[k]
		a[0][0] = x;
		a[0][1] = -x;
		a[0][2] = 0;
		a[1][1] = -2 * x;
		a[1][2] = -x;
		a[2][2] = x;
	}
	void change(int x)
	{
		a[0][0] += x;
		a[0][1] -= x;
		a[1][1] -= 2 * x;
		a[1][2] -= x;
		a[2][2] += x;
	}
};
info operator+(info a, info b)
{
	if (a.a[0][0] < 0) return b;
	if (b.a[0][0] < 0) return a;
	info res;
	for (int i = 0; i < 3; i++)
	{
		for (int j = i; j < 3; j++)
		{
			res.a[i][j] = max(a.a[i][j], b.a[i][j]);
			for (int k = i + 1; k <= j; k++)
			{
				ckmax(res.a[i][j], a.a[i][k - 1] + b.a[k][j]);
			}
		}
	}
	return res;
}
info st[1 << 19];
void down(int id)
{
	if (!lz[id]) return;
	for (int i : {id << 1, id << 1 | 1})
	{
		lz[i] += lz[id];
		st[i].change(lz[id]);
	}
	lz[id] = 0;
}
void init(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 18)
{
	if (r < u || l > v) return;
	if (l >= u && r <= v) 
	{
		st[id] = info(x);
		return;
	}
	int mid = (l + r) >> 1;
	down(id);
	init(u, v, x, id << 1, l, mid);
	init(u, v, x, id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 18)
{
	if (r < u || l > v) return;
	if (l >= u && r <= v) 
	{
		lz[id] += x;
		st[id].change(x);
		return;
	}
	int mid = (l + r) >> 1;
	down(id);
	update(u, v, x, id << 1, l, mid);
	update(u, v, x, id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, q, _w;
	cin >> n >> q >> _w;
	vector<int> et = {0}, w(n), h(n), val(n);
	vector<vector<pair<int, int>>> adj(n);
	vector<tuple<int, int, int>> e;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, ww;
		cin >> u >> v >> ww;
		u--, v--;
		adj[u].emplace_back(v, ww);
		adj[v].emplace_back(u, ww);
		e.emplace_back(u, v, ww);
	} 
	function<void(int, int)> dfs = [&](int u, int p)
	{
		et.push_back(u);
		for (auto [v, ww] : adj[u])
		{
			if (v == p) continue;
			h[v] = h[u] + 1;
			val[v] = ww;
			w[v] = w[u] + ww;
			dfs(v, u);
			et.push_back(u);
		}
	};
	dfs(0, 0);
	for (int i = 1; i < et.size(); i++)
	{
		init(i, i, w[et[i]]);
	}
	vector<int> in(n, -1), out(n);
	for (int i = 1; i < et.size(); i++)
	{
		out[et[i]] = i;
		if (in[et[i]] == -1) in[et[i]] = i;
	}
	for (auto &[u, v, ww] : e)
	{
		if (h[u] < h[v]) swap(u, v);
	}
	int last = 0;
	while (q--)
	{
		int i, x;
		cin >> i >> x;
		i = (i + last) % (n - 1);
		x = (x + last) % _w;
		int u = get<0>(e[i]);
		int dif = x - val[u];
		update(in[u], out[u], dif);
		val[u] = x;
		//cout << dif << '\n';
		last = st[1].a[0][2];
		cout << last << '\n';
	}
	return 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