Submission #239176

#	Time	Username	Problem	Language	Result	Execution time	Memory
239176		crackersamdjam	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	5070 ms	150232 KiB

diameter

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

typedef long long ll;
typedef long long T;
constexpr int MM = 1e5+2, LOG = 17;

int n, q, tot, sz[MM], a[MM], b[MM], dep[LOG][MM], in[LOG][MM], out[LOG][MM], t[LOG], centid[LOG][MM], parid[LOG][MM];
ll maxw, c[MM];
std::vector<std::pair<int, ll>> adj[MM];
bool vis[MM];
//all best, ch set for each node as centroid

struct Combine {
	using Data = ll;
	using Lazy = ll;
	const Data qdef = 0;
	const Lazy ldef = 0;
	Data merge(const Data &l, const Data &r) const { return std::max(l, r); }
	Data applyLazy(const Data &l, const Lazy &r) const { return l + r; }
	Lazy getSegmentVal(const Lazy &v, int k) const { return v; }
	Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return l + r; }
};
struct Combine2 {
	using Data = std::pair<ll, ll>;
	using Lazy = ll;
	const Data qdef = {0, 0};
	const Lazy ldef = 0;
	Data merge(const Data &l, const Data &r) const {
		std::vector<ll> v = {l.first, l.second, r.first, r.second};
		sort(all(v), std::greater<ll>());
		return {v[0], v[1]};
	}
	Data applyLazy(const Data &l, const Lazy &r) const {
		return {r, 0}; //root node
	}
	Lazy getSegmentVal(const Lazy &v, int k) const { return v; }
	Lazy mergeLazy(const Lazy &l, const Lazy &r) const {
		return r;
	}
};
// Time Complexity:
//   constructor: O(N)
//   update, query: O(log N)
// Memory Complexity: O(N)
// Tested:
//   https://dmoj.ca/problem/dmopc17c4p6
//   https://dmoj.ca/problem/dmopc18c5p5
//   https://dmoj.ca/problem/dmopc18c6p5
//   https://dmoj.ca/problem/lazy
//   https://mcpt.ca/problem/seq3
template <class Combine> struct SegmentTreeLazyBottomUp {
	using Data = typename Combine::Data; using Lazy = typename Combine::Lazy;
	Combine C; int N, lgN; std::vector<Data> TR; std::vector<Lazy> LZ;
	void apply(int i, const Lazy &v, int k) {
		TR[i] = C.applyLazy(TR[i], C.getSegmentVal(v, k));
		if (i < N) LZ[i] = C.mergeLazy(LZ[i], v);
	}
	void pushup(int i) {
		for (int k = 2; i /= 2; k *= 2) {
			TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
			if (LZ[i] != C.ldef)
				TR[i] = C.applyLazy(TR[i], C.getSegmentVal(LZ[i], k));
		}
	}
	void propagate(int i) {
		int h = lgN + 1, k = 1 << lgN, ii = i >> h;
		for (; h > 0; ii = i >> --h, k /= 2){
//			std::cout<<LZ[ii]<<std::endl;
//			std::cout<<C.ldef<<std::endl;
			if (LZ[ii] != C.ldef) {
				apply(ii * 2, LZ[ii], k); apply(ii * 2 + 1, LZ[ii], k); LZ[ii] = C.ldef;
			}
		}
	}
	void init(int n0, const Data vdef) {
		N = n0;
		lgN = std::__lg(N);
		TR = std::vector<Data>(N * 2, C.qdef);
		LZ = std::vector<Lazy>(N, C.ldef);
		fill(TR.begin() + N, TR.end(), vdef);
		for (int i = N - 1; i > 0; i--) TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
	}
	void update(int l, int r, const Lazy &v) {
		int l0 = l += N, r0 = r += N, k = 1; propagate(l); propagate(r);
		for (; l <= r; l /= 2, r /= 2, k *= 2) {
			if (l & 1) apply(l++, v, k);
			if (!(r & 1)) apply(r--, v, k);
		}
		pushup(l0); pushup(r0);
	}
	Data query(int l, int r) {
		propagate(l += N); propagate(r += N); Data ql = C.qdef, qr = C.qdef;
		for (; l <= r; l /= 2, r /= 2) {
			if (l & 1) ql = C.merge(ql, TR[l++]);
			if (!(r & 1)) qr = C.merge(TR[r--], qr);
		}
		return C.merge(ql, qr);
	}
};
SegmentTreeLazyBottomUp<Combine> ST[LOG];
SegmentTreeLazyBottomUp<Combine2> BEST, CH[LOG];

int getsz(int cur, int pre){
	sz[cur] = 1;
	for(auto e: adj[cur]){
		int u = e.first;
		if(u != pre && !vis[u])
			sz[cur] += getsz(u, cur);
	}
	return sz[cur];
}

int findcent(int cur, int pre){
	for(auto e: adj[cur]){
		int u = e.first;
		if(!vis[u] && u != pre && sz[u]*2 > tot)
			return findcent(u, cur);
	}
	return cur;
}

void dfs1(int cur, int pre, int lvl, int cent, ll w){
	in[lvl][cur] = ++t[lvl];
	dep[lvl][cur] = dep[lvl][pre]+1;
	centid[lvl][cur] = cent;
	parid[lvl][cur] = pre == cent ? cur : parid[lvl][pre];
	for(auto u: adj[cur]){
		if(u.first == pre || vis[u.first])
			continue;
		dfs1(u.first, cur, lvl, cent, u.second);
	}
	out[lvl][cur] = t[lvl];
	ST[lvl].update(in[lvl][cur], out[lvl][cur], w);
}

void go(int root, int lvl){
	getsz(root, -1);
	tot = sz[root];
	if(tot == 1)
		return;
	int cent = findcent(root, -1);
	vis[cent] = 1;
	
	dfs1(cent, 0, lvl, cent, 0);
	
	for(auto u: adj[cent]){
		if(vis[u.first])
			continue;
		int st = in[lvl][u.first], ed = out[lvl][u.first];
		ll v = ST[lvl].query(st, ed);
		CH[lvl].update(in[lvl][u.first], in[lvl][u.first], v);
//		print(lvl, u.first, v);
//		ch[cent].insert(v);
	}
//	while(ch[cent].size() < 2)
//		ch[cent].insert(0);
	
//	auto ptr = ch[cent].begin();
//	best.insert(*ptr + *++ptr);
	auto tmp = CH[lvl].query(in[lvl][cent], out[lvl][cent]);
//	print(in[lvl][cent], out[lvl][cent]);
//	print(tmp.first, tmp.second);
	BEST.update(cent, cent, tmp.first+tmp.second);

	for(auto u: adj[cent]){
		if(!vis[u.first])
			go(u.first, lvl+1);
	}
}

int main(){
	scan(n, q, maxw);
	for(int i = 0; i < n-1; i++){
		scan(a[i], b[i], c[i]);
		adj[a[i]].emplace_back(b[i], c[i]);
		adj[b[i]].emplace_back(a[i], c[i]);
	}
	
	for(int i = 0; i < LOG; i++){
		ST[i].init(MM, 0);
		CH[i].init(MM, {0, 0});
	}
	BEST.init(MM, {0, 0});
	
	go(1, 0);
	
	ll d, e, last = 0;
	while(q--){
		scan(d, e);
		d = (d+last)%(n-1);
		e = (e+last)%maxw;
		int aa = a[d], bb = b[d];
		
		ll dif = e-c[d];
		c[d] = e;
		
		for(int i = 0; i < LOG; i++){
			int cent = centid[i][aa];
			if(cent and cent == centid[i][bb]){
				if(dep[i][aa] < dep[i][bb])
					std::swap(aa, bb);
				//aa is deeper, update it
				
//				auto ptr = ch[cent].begin();
//				best.erase(best.lower_bound(*ptr + *++ptr));
				
				int par = parid[i][aa];
				
//				ch[cent].erase(ch[cent].lower_bound(ST[i].query(in[i][par], out[i][par])));
				ST[i].update(in[i][aa], out[i][aa], dif);
//				ch[cent].insert(ST[i].query(in[i][par], out[i][par]));]
				ll v = ST[i].query(in[i][par], out[i][par]);
				CH[i].update(in[i][par], in[i][par], v); //okay...
				
				auto tmp = CH[i].query(in[i][cent], out[i][cent]);
				BEST.update(cent, cent, tmp.first+tmp.second);
//				print(tmp.first, tmp.second);
//				ptr = ch[cent].begin();
//				best.insert(*ptr + *++ptr);
			}
		}
//		print(last = *best.begin());
		print(last = BEST.query(1, n).first);
	}
}
/*
 * ett each centroid
 * when update edge, loop through LOG levels
 * if for any lvl, there is a point where centid[lvl][a] == centid[lvl][b] != 0, then update the one with higher depth
 * then for its centid, remove old ans from multiset and insert new one
 *
 */

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