Submission #674484

#	Time	Username	Problem	Language	Result	Execution time	Memory
674484		Sohsoh84	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	4662 ms	371744 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;
#define int			ll

const ll MAXN = 1e5 + 10;
const ll LOG = 40;
const ll INF = 1e18;

int n, q, t, cent_par[MAXN], H[MAXN], D[MAXN][LOG], sz[MAXN], 
    tin[MAXN][LOG], tout[MAXN][LOG], EV[MAXN], EU[MAXN];
ll w, lz[MAXN * LOG * 4], ans[MAXN], EW[MAXN];
pair<pll, pll> A[MAXN * LOG], sg[MAXN * LOG * 4];
vector<pll> adj[MAXN];
bool B[MAXN];

int dfs_sz(int v, int p) {
	sz[v] = 1;
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p)
			sz[v] += dfs_sz(u, v);
	
	return sz[v];
}

int centroid(int v, int p, int tn) {
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p && sz[u] * 2 > tn)
			return centroid(u, v, tn);

	return v;
}

void dfs(int v, int p, int lvl, ll d, int typ) {
	tin[v][lvl] = ++t;
	A[t] = {{d, typ}, {-INF, -1}};
	D[v][lvl] = D[p][lvl] + 1;

	for (auto [u, w] : adj[v])
		if (!B[u] && u != p)
			dfs(u, v, lvl, d + w, typ);

	tout[v][lvl] = t;
}

void build_tree(int v, int p, int lvl) {
	v = centroid(v, 0, dfs_sz(v, 0));

	cent_par[v] = p;
	H[v] = lvl;
	B[v] = true;

	tin[v][lvl] = ++t;
	D[v][lvl] = 0;
	A[t] = {{0, v}, {-INF, -1}};
	for (auto [u, w] : adj[v])
		if (!B[u])
			dfs(u, v, lvl, w, u);
	tout[v][lvl] = t;

	for (auto [u, w] : adj[v])
		if (!B[u])
			build_tree(u, v, lvl + 1);
}

inline void push(int v) {
	sg[v].X.X += lz[v];
	sg[v].Y.X += lz[v];
	if (v < (MAXN * LOG * 4))
		lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];

	lz[v] = 0;
}

inline void add(pair<pll, pll>& a, pll b) {
	if (b.X > a.X.X) {
		if (b.Y != a.X.Y) a.Y = a.X;
		a.X = b;
	} else if (b.X > a.Y.X && b.Y != a.X.Y) {
		a.Y = b;
	}
}

inline pair<pll, pll> merge(pair<pll, pll> a, pair<pll, pll> b) {
	add(a, b.X);
	add(a, b.Y);
	return a;
}

void build(int l = 1, int r = t, int v = 1) {
	if (l == r) sg[v] = A[l];
	else {
		int mid = (l + r) >> 1;
		build(l, mid, v << 1);
		build(mid + 1, r, v << 1 | 1);
		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}
}

void update(int ql, int qr, ll val, int l = 1, int r = t, int v = 1) {
	push(v);
	if (ql > r || qr < l) return;
	if (ql <= l && qr >= r) {
		lz[v] += val;
		push(v);
		return;
	}

	int mid = (l + r) >> 1;
	update(ql, qr, val, l, mid, v << 1);
	update(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}

pair<pll, pll> query(int ql, int qr, int l = 1, int r = t, int v = 1) {
	push(v);
	if (ql > r || qr < l) return {{-INF, -INF}, {-INF, -INF - 1}};
	if (ql <= l && qr >= r) return sg[v];
	
	int mid = (l + r) >> 1;
	return merge(query(ql, qr, l, mid, v << 1),
			 query(ql, qr, mid + 1, r, v << 1 | 1));
}

set<pll> ans_st;

void update_ans(int v) {
	ans_st.erase({ans[v], v});
	auto e = query(tin[v][H[v]], tout[v][H[v]]);
	ans[v] = max(max(0ll, e.X.X), e.X.X + e.Y.X);
	ans_st.insert({ans[v], v});
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q >> w;
	for (int i = 0; i < n - 1; i++) {
		cin >> EV[i] >> EU[i] >> EW[i];
		adj[EU[i]].push_back({EV[i], EW[i]});
		adj[EV[i]].push_back({EU[i], EW[i]});
	}

	build_tree(1, 0, 0);
	build();
	for (int v = 1; v <= n; v++) update_ans(v);

	ll last = 0;
	while (q--) {
		ll td, tw, ind, delta, rw, u, v;
		cin >> td >> tw;
		
		ind = (td + last) % (n - 1), rw = (tw + last) % w;
		u = EU[ind], v = EV[ind];
		delta = (rw - EW[ind]);
		EW[ind] = rw;

		if (H[u] > H[v]) swap(u, v);
	
		int c = u;
		while (c) {
			int au = u, av = v, lvl = H[c];
			if (D[au][lvl] > D[av][lvl]) swap(au, av);

			update(tin[av][lvl], tout[av][lvl], delta);
			update_ans(c);
			c = cent_par[c];
		}

		last = ans_st.rbegin() -> X;
		cout << last << endl;
	}
	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