Submission #555377

#	Time	Username	Problem	Language	Result	Execution time	Memory
555377		sidon	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2117 ms	188872 KiB

diameter

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
 
const int Z = 1e5, B = 17, INF = 1e18+1;
 
array<int, 2> operator+(const int &x, array<int, 2> y) {
	y[0] += x;
	return y;
}
 
struct SegmentTree {
	int n, *add;
	array<int, 2> *val;
	int sL, sR, sV;
	SegmentTree(int N) : n(2<<__lg(N-1)), add(new int[2*n] {}), val(new array<int, 2> [2*n] {}) {
		for(int i = n - 1; i < 2*n; ++i) val[i][0] = -INF;
	}
	void assign(const int &i, const array<int, 2> &v) {
		val[n+i-1] = v;
	}
	void build() {
		for(int i = n-1; i--; ) val[i] = max(val[2*i+1], val[2*i+2]);
	}
	void update(int l, int r, int v) {
		sL = l, sR = r + 1, sV = v;
		upd(0, 0, n);
	}
	void upd(int x, int l, int r) {
		if(sL <= l && r <= sR) {
			val[x][0] += sV;
			add[x] += sV;
			return;
		}
		if(sR <= l || r <= sL) return;
		int m = (l + r) / 2;
		upd(2*x+1, l, m);
		upd(2*x+2, m, r);
 
		val[x] = add[x] + max(val[2*x+1], val[2*x+2]);
	}
	array<int, 2> queryOut(int l, int r) {
		return max(query(0, l - 1), query(r + 1, n - 1));
	}
	array<int, 2> query(int l, int r) {
		sL = l, sR = r + 1;
		return qry(0, 0, n);
	}
	array<int, 2> qry(int x, int l, int r) {
		if(sL <= l && r <= sR) return val[x];
		if(sR <= l || r <= sL) return {-INF};
		int m = (l + r) / 2;
		return add[x] + max(qry(2*x+1, l, m), qry(2*x+2, m, r));
	}
}* seg[Z];
 
int n, q, wLim, w[Z], sz[Z], par[Z];
array<int, 2> edge[Z];
vector<pair<int, int>> g[Z];
bool vis[Z];
 
void init(int u, int p) {
	sz[u] = 1;
	for(const auto &[v, e] : g[u]) if(v != p)
		init(v, u), sz[u] += sz[v];
}
 
int r, h, curSize, curSub, dfsTimer, id[B][Z], L[B][Z], R[B][Z], sub[B][Z];
 
int find(int u) {
	for(const auto &[v, e] : g[u]) if(!vis[v] && sz[v] > curSize / 2) {
		sz[u] -= sz[v];
		sz[v] = curSize;
		return find(v);
	}
	return u;
}
 
void dfs(int u, int p, int d) {
	L[h][u] = dfsTimer++;
	for(const auto &[v, e] : g[u]) if(!vis[v] && v != p) {
		if(u == r) curSub = v;
		dfs(v, u, d + w[e]);
	}
	R[h][u] = dfsTimer-1;
 
	sub[h][u] = u == r ? r : curSub;
	id[h][u] = r;
	seg[r]->assign(L[h][u], {d, u});
}
 
void decompose(int u, int _h) {
	curSize = sz[u];
	vis[u = r = find(u)] = 1;
 
	h = _h, dfsTimer = 0;
	seg[r] = new SegmentTree(sz[r]);
	dfs(r, r, 0);
	seg[r]->build();
 
	for(const auto &[v, e] : g[u]) if(!vis[v])
		decompose(v, _h + 1);
}
 
array<int, 3> diam {-1};
int _r;
 
void initDiam(int u, int p, int d) {
	diam = max(diam, {d, _r, u});
	for(const auto &[v, e] : g[u]) if(v != p)
		initDiam(v, u, d + w[e]);
}
 
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> wLim;
 
	for(int i = 0; i + 1 < n; ++i) {
		auto &[u, v] = edge[i];
		cin >> u >> v >> w[i];
		--u, --v;
		g[u].emplace_back(v, i);
		g[v].emplace_back(u, i);
	}
	for(int i = 0; i < B; ++i)
		fill(id[i], id[i] + n, -1);
 
	init(0, 0);
	decompose(0, 0);
 
	initDiam(_r = diam[2], -1, 0);
	initDiam(_r = diam[2], -1, 0);
 
	for(int last {}; q--; ) {
		int qD, qE; cin >> qD >> qE;
		(qD += last) %= n - 1;
		(qE += last) %= wLim;
 
		auto [u, v] = edge[qD];
 
		for(int i = 0; i < B; ++i) if(id[i][u] >= 0 && id[i][u] == id[i][v]) {
			if(L[i][u] > L[i][v]) swap(u, v);
			seg[id[i][u]]->update(L[i][v], R[i][v], qE - w[qD]);
		}
		w[qD] = qE;
 
		array<int, 2> chk = {diam[1], diam[2]};
		diam[0] = -1;
		for(const int &c : chk) {
			array<int, 2> best {-1};
			for(int i = B; i--; ) if(id[i][c] >= 0) {
				auto cur = seg[id[i][c]]->queryOut(L[i][sub[i][c]], R[i][sub[i][c]]);
				cur[0] += seg[id[i][c]]->query(L[i][c], L[i][c])[0];
 
				best = max(best, cur);
			}
 
			diam = max(diam, {best[0], best[1], c});
		}
		cout << (last = diam[0]) << '\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