oj.uz

Submission #239178

# Submission time Handle Problem Language Result Execution time Memory
239178 2020-06-14T17:10:58 Z crackersamdjam Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 4014 ms 143652 KB 
#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 = std::pair<ll, ll>;
	const Data qdef = {0LL, 0LL};
	Data merge(const Data &l, const Data &r) const {
		if(l.first > r.first)
			return {l.first, std::max(l.second, r.first)};
		return {r.first, std::max(r.second, l.first)};
	}
	Data applyLazy(const Data &l, const Lazy &r) const {
		return r;
	}
};
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) 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);
	}
};
template <class Combine> struct SegmentTreeBottomUp {
	using Data = typename Combine::Data; using Lazy = typename Combine::Lazy;
	Combine C; int N; std::vector<Data> TR;
	void init(int N0, const Data &vdef) {
		N = N0;
		TR = std::vector<Data>(N * 2, C.qdef);
		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 i, const Lazy &v) {
		for (i += N, TR[i] = C.applyLazy(TR[i], v); i /= 2;)
			TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
	}
	Data query(int l, int r) {
		Data ql = C.qdef, qr = C.qdef;
		for (l += N, r += N; 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];
SegmentTreeBottomUp<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], {v, 0LL});
//		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, {tmp.first+tmp.second, 0LL});

	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], {v, 0LL});
				
				auto tmp = CH[i].query(in[i][cent], out[i][cent]);
				BEST.update(cent, {tmp.first+tmp.second, 0LL});
//				print(tmp.first, tmp.second);
//				ptr = ch[cent].begin();
//				best.insert(*ptr + *++ptr);
			}
		}
//		print(last = *best.begin());
		print(last = BEST.query(0, MM-1).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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 99192 KB Output is correct
2 Correct 58 ms 99064 KB Output is correct
3 Correct 57 ms 99192 KB Output is correct
4 Correct 57 ms 99192 KB Output is correct
5 Correct 65 ms 99196 KB Output is correct
6 Correct 59 ms 99064 KB Output is correct
7 Correct 60 ms 99192 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 57 ms 99320 KB Output is correct
10 Correct 57 ms 99320 KB Output is correct
11 Correct 58 ms 99192 KB Output is correct
12 Correct 59 ms 99192 KB Output is correct
13 Correct 58 ms 99320 KB Output is correct
14 Correct 57 ms 99192 KB Output is correct
15 Correct 60 ms 99320 KB Output is correct
16 Correct 66 ms 99192 KB Output is correct
17 Correct 58 ms 99320 KB Output is correct
18 Correct 57 ms 99320 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 99192 KB Output is correct
2 Correct 58 ms 99064 KB Output is correct
3 Correct 57 ms 99192 KB Output is correct
4 Correct 57 ms 99192 KB Output is correct
5 Correct 65 ms 99196 KB Output is correct
6 Correct 59 ms 99064 KB Output is correct
7 Correct 60 ms 99192 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 57 ms 99320 KB Output is correct
10 Correct 57 ms 99320 KB Output is correct
11 Correct 58 ms 99192 KB Output is correct
12 Correct 59 ms 99192 KB Output is correct
13 Correct 58 ms 99320 KB Output is correct
14 Correct 57 ms 99192 KB Output is correct
15 Correct 60 ms 99320 KB Output is correct
16 Correct 66 ms 99192 KB Output is correct
17 Correct 58 ms 99320 KB Output is correct
18 Correct 57 ms 99320 KB Output is correct
19 Correct 81 ms 99576 KB Output is correct
20 Correct 87 ms 99576 KB Output is correct
21 Correct 87 ms 99788 KB Output is correct
22 Correct 90 ms 99704 KB Output is correct
23 Correct 90 ms 100600 KB Output is correct
24 Correct 121 ms 100856 KB Output is correct
25 Correct 123 ms 101024 KB Output is correct
26 Correct 122 ms 101240 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 99192 KB Output is correct
2 Correct 59 ms 99192 KB Output is correct
3 Correct 61 ms 99192 KB Output is correct
4 Correct 67 ms 99192 KB Output is correct
5 Correct 117 ms 99576 KB Output is correct
6 Correct 67 ms 99192 KB Output is correct
7 Correct 57 ms 99196 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 59 ms 99192 KB Output is correct
10 Correct 78 ms 99320 KB Output is correct
11 Correct 117 ms 99704 KB Output is correct
12 Correct 60 ms 99576 KB Output is correct
13 Correct 60 ms 99632 KB Output is correct
14 Correct 61 ms 99576 KB Output is correct
15 Correct 80 ms 99704 KB Output is correct
16 Correct 130 ms 100088 KB Output is correct
17 Correct 110 ms 107876 KB Output is correct
18 Correct 103 ms 107748 KB Output is correct
19 Correct 105 ms 107752 KB Output is correct
20 Correct 145 ms 107876 KB Output is correct
21 Correct 238 ms 108556 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 99576 KB Output is correct
2 Correct 85 ms 99552 KB Output is correct
3 Correct 211 ms 99976 KB Output is correct
4 Correct 331 ms 100088 KB Output is correct
5 Correct 95 ms 102392 KB Output is correct
6 Correct 144 ms 102392 KB Output is correct
7 Correct 375 ms 102636 KB Output is correct
8 Correct 589 ms 102904 KB Output is correct
9 Correct 241 ms 116220 KB Output is correct
10 Correct 343 ms 116344 KB Output is correct
11 Correct 734 ms 116732 KB Output is correct
12 Correct 1075 ms 116900 KB Output is correct
13 Correct 453 ms 134908 KB Output is correct
14 Correct 548 ms 134776 KB Output is correct
15 Correct 949 ms 135172 KB Output is correct
16 Correct 1452 ms 135432 KB Output is correct
17 Correct 2729 ms 135756 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 136320 KB Output is correct
2 Correct 2476 ms 137436 KB Output is correct
3 Correct 2334 ms 135864 KB Output is correct
4 Correct 2393 ms 137708 KB Output is correct
5 Correct 2635 ms 135796 KB Output is correct
6 Correct 2088 ms 137284 KB Output is correct
7 Correct 3435 ms 141992 KB Output is correct
8 Correct 3216 ms 141828 KB Output is correct
9 Correct 3396 ms 141856 KB Output is correct
10 Correct 3631 ms 141856 KB Output is correct
11 Correct 3154 ms 141428 KB Output is correct
12 Correct 2852 ms 141560 KB Output is correct
13 Correct 3688 ms 143548 KB Output is correct
14 Correct 3684 ms 143364 KB Output is correct
15 Correct 3784 ms 143652 KB Output is correct
16 Correct 4014 ms 143432 KB Output is correct
17 Correct 3656 ms 143384 KB Output is correct
18 Correct 3079 ms 143092 KB Output is correct
19 Correct 3660 ms 143468 KB Output is correct
20 Correct 3748 ms 143440 KB Output is correct
21 Correct 3652 ms 143488 KB Output is correct
22 Correct 3889 ms 143516 KB Output is correct
23 Correct 3887 ms 143416 KB Output is correct
24 Correct 3047 ms 142952 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 99192 KB Output is correct
2 Correct 58 ms 99064 KB Output is correct
3 Correct 57 ms 99192 KB Output is correct
4 Correct 57 ms 99192 KB Output is correct
5 Correct 65 ms 99196 KB Output is correct
6 Correct 59 ms 99064 KB Output is correct
7 Correct 60 ms 99192 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 57 ms 99320 KB Output is correct
10 Correct 57 ms 99320 KB Output is correct
11 Correct 58 ms 99192 KB Output is correct
12 Correct 59 ms 99192 KB Output is correct
13 Correct 58 ms 99320 KB Output is correct
14 Correct 57 ms 99192 KB Output is correct
15 Correct 60 ms 99320 KB Output is correct
16 Correct 66 ms 99192 KB Output is correct
17 Correct 58 ms 99320 KB Output is correct
18 Correct 57 ms 99320 KB Output is correct
19 Correct 81 ms 99576 KB Output is correct
20 Correct 87 ms 99576 KB Output is correct
21 Correct 87 ms 99788 KB Output is correct
22 Correct 90 ms 99704 KB Output is correct
23 Correct 90 ms 100600 KB Output is correct
24 Correct 121 ms 100856 KB Output is correct
25 Correct 123 ms 101024 KB Output is correct
26 Correct 122 ms 101240 KB Output is correct
27 Correct 67 ms 99192 KB Output is correct
28 Correct 59 ms 99192 KB Output is correct
29 Correct 61 ms 99192 KB Output is correct
30 Correct 67 ms 99192 KB Output is correct
31 Correct 117 ms 99576 KB Output is correct
32 Correct 67 ms 99192 KB Output is correct
33 Correct 57 ms 99196 KB Output is correct
34 Correct 57 ms 99192 KB Output is correct
35 Correct 59 ms 99192 KB Output is correct
36 Correct 78 ms 99320 KB Output is correct
37 Correct 117 ms 99704 KB Output is correct
38 Correct 60 ms 99576 KB Output is correct
39 Correct 60 ms 99632 KB Output is correct
40 Correct 61 ms 99576 KB Output is correct
41 Correct 80 ms 99704 KB Output is correct
42 Correct 130 ms 100088 KB Output is correct
43 Correct 110 ms 107876 KB Output is correct
44 Correct 103 ms 107748 KB Output is correct
45 Correct 105 ms 107752 KB Output is correct
46 Correct 145 ms 107876 KB Output is correct
47 Correct 238 ms 108556 KB Output is correct
48 Correct 62 ms 99576 KB Output is correct
49 Correct 85 ms 99552 KB Output is correct
50 Correct 211 ms 99976 KB Output is correct
51 Correct 331 ms 100088 KB Output is correct
52 Correct 95 ms 102392 KB Output is correct
53 Correct 144 ms 102392 KB Output is correct
54 Correct 375 ms 102636 KB Output is correct
55 Correct 589 ms 102904 KB Output is correct
56 Correct 241 ms 116220 KB Output is correct
57 Correct 343 ms 116344 KB Output is correct
58 Correct 734 ms 116732 KB Output is correct
59 Correct 1075 ms 116900 KB Output is correct
60 Correct 453 ms 134908 KB Output is correct
61 Correct 548 ms 134776 KB Output is correct
62 Correct 949 ms 135172 KB Output is correct
63 Correct 1452 ms 135432 KB Output is correct
64 Correct 2729 ms 135756 KB Output is correct
65 Correct 2312 ms 136320 KB Output is correct
66 Correct 2476 ms 137436 KB Output is correct
67 Correct 2334 ms 135864 KB Output is correct
68 Correct 2393 ms 137708 KB Output is correct
69 Correct 2635 ms 135796 KB Output is correct
70 Correct 2088 ms 137284 KB Output is correct
71 Correct 3435 ms 141992 KB Output is correct
72 Correct 3216 ms 141828 KB Output is correct
73 Correct 3396 ms 141856 KB Output is correct
74 Correct 3631 ms 141856 KB Output is correct
75 Correct 3154 ms 141428 KB Output is correct
76 Correct 2852 ms 141560 KB Output is correct
77 Correct 3688 ms 143548 KB Output is correct
78 Correct 3684 ms 143364 KB Output is correct
79 Correct 3784 ms 143652 KB Output is correct
80 Correct 4014 ms 143432 KB Output is correct
81 Correct 3656 ms 143384 KB Output is correct
82 Correct 3079 ms 143092 KB Output is correct
83 Correct 3660 ms 143468 KB Output is correct
84 Correct 3748 ms 143440 KB Output is correct
85 Correct 3652 ms 143488 KB Output is correct
86 Correct 3889 ms 143516 KB Output is correct
87 Correct 3887 ms 143416 KB Output is correct
88 Correct 3047 ms 142952 KB Output is correct
89 Correct 2469 ms 136844 KB Output is correct
90 Correct 2613 ms 139664 KB Output is correct
91 Correct 3079 ms 140856 KB Output is correct
92 Correct 3190 ms 141584 KB Output is correct
93 Correct 3535 ms 142104 KB Output is correct
94 Correct 3498 ms 143640 KB Output is correct
95 Correct 3669 ms 143204 KB Output is correct
96 Correct 3650 ms 143380 KB Output is correct
97 Correct 3653 ms 143328 KB Output is correct
98 Correct 3658 ms 143260 KB Output is correct
99 Correct 3759 ms 143368 KB Output is correct
100 Correct 3708 ms 143324 KB Output is correct