oj.uz

Submission #619073

# Submission time Handle Problem Language Result Execution time Memory
619073 2022-08-02T09:41:38 Z MetalPower Dynamic Diameter (CEOI19_diameter) C++14
100 / 100
 4887 ms 127876 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, ll>
#define pli pair<ll, ll>
#define fi first
#define se second

const int MX = 1e5 + 10;
const int LG = 17;
const ll INF = 1e18 + 7;

int N, Q; ll W;
vector<int> adj[MX];
vector<pair<pli, ll>> edges;

int sz[MX], dead[MX];

void dfs(int u, int v){
	sz[u] = 1;
	for(int nx : adj[u]){
		if(nx == v || dead[nx]) continue;
		dfs(nx, u);
		sz[u] += sz[nx];
	}
}

int cent = -1, ccsize = 0;

void dfc(int u, int v){
	for(int nx : adj[u]){
		if(nx == v || dead[nx]) continue;
		dfc(nx, u);
	}
	if(cent == -1 && sz[u] >= (ccsize + 1) / 2) cent = u;
}

int layer = 0, tim[LG], in[MX][LG], fn[MX][LG], root[MX][LG], par[MX][LG], lnum[MX];

// Centroid Decomposition Layer
	// Euler Tour (in, out) for each layer
	// Root (Centroid) for each layer
	// Parent (if Centroid is root) for each layer

void init(int u, int v){
	root[u][layer] = cent;
	par[u][layer] = v;
	in[u][layer] = ++tim[layer];
	for(int nx : adj[u]){
		if(nx == v || dead[nx]) continue;
		init(nx, u); 
	}
	fn[u][layer] = tim[layer];
}

#define psi pair<int, int>

vector<psi> adt[MX];

void findCentroid(int u){
	
	dfs(u, 0);
	ccsize = sz[u], cent = -1;
	dfc(u, 0);

	// cout << "Centroid is " << cent << '\n';

	{
		init(cent, 0); lnum[cent] = layer;
		for(int nx : adj[cent])
			if(!dead[nx]) adt[cent].push_back({in[nx][layer], nx});
		sort(adt[cent].begin(), adt[cent].end());
	}

	{
		dead[cent] = true;
		for(int nx : adj[cent]){
			if(dead[nx]) continue;
			layer++; findCentroid(nx); layer--;
		}
	}
}

struct itseg{

	ll st[MX << 1];

	void upd(int p, ll v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = max(st[p << 1], st[p << 1|1]);
	}

	ll que(int l, int r){
		ll res = 0;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = max(res, st[l++]);
			if(r & 1) res = max(res, st[--r]);
		}
		return res;
	}
} superseg;

struct segtree{

	ll st[MX << 2], lz[MX << 2];

	void prop(int id, int l, int r){
		if(lz[id] == 0) return;
		st[id] += lz[id];
		if(l != r){
			lz[id << 1] += lz[id];
			lz[id << 1|1] += lz[id];
		}
		lz[id] = 0;
	}

	void upd(int id, int l, int r, int from, int to, ll v){
		prop(id, l, r);
		if(r < from || l > to) return;
		if(from <= l && r <= to){
			lz[id] += v;
			prop(id, l, r);
		}else{
			int mid = l + r >> 1;
			upd(id << 1, l, mid, from, to, v);
			upd(id << 1|1, mid + 1, r, from, to, v);
			st[id] = max(st[id << 1], st[id << 1|1]);
		}
	}

	ll query(int id, int l, int r, int from, int to){
		prop(id, l, r);
		if(r < from || l > to) return -INF;
		if(from <= l && r <= to){
			return st[id];
		}else{
			int mid = l + r >> 1;
			return max(
				query(id << 1, l, mid, from, to),
				query(id << 1|1, mid + 1, r, from, to)
			);
		}
	}

} seg[LG];

set<pli> dep[MX];
// vector<int> adt[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> Q >> W;
	for(int i = 1; i < N; i++){
		int u, v; ll w; cin >> u >> v >> w;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({{u, v}, w});
	}

	// cout << "find Centroid" << '\n';
	findCentroid(1);

	for(auto x : edges){
		int u = x.fi.fi, v = x.fi.se; 
		ll w = x.se;
		for(int j = 0; j < LG; j++){
			if(root[u][j] != root[v][j]) break;
			if(in[u][j] < in[v][j]) seg[j].upd(1, 1, N, in[v][j], fn[v][j], w);
			else seg[j].upd(1, 1, N, in[u][j], fn[u][j], w);
		}
	}

	for(int i = 1; i <= N; i++){

		int lyr = lnum[i];
		for(psi& nx : adt[i]) dep[i].insert({seg[lyr].query(1, 1, N, in[nx.se][lyr], fn[nx.se][lyr]), in[nx.se][lyr]});

		{
			ll ans = 0;
			set<pli>::iterator it = dep[i].end(); 

			if(it != dep[i].begin()){
				it--;
				ans += (*it).fi;
			}

			if(it != dep[i].begin()){
				it--;
				ans += (*it).fi;
			}

			superseg.upd(i, ans);
			// cout << "answer for centroid " << i << " is " << ans << '\n';
		}
	}

	// cout << "update depths" << '\n';

	ll last = 0;
	for(int i = 0; i < Q; i++){

		int idx; ll nw; cin >> idx >> nw;
		idx = (int)((last + idx) % (N - 1));
		nw = (last + nw) % W;

		int u = edges[idx].fi.fi, v = edges[idx].fi.se;
		ll df = nw - edges[idx].se;

		// cout << "update edge " << u << " " << v << '\n';

		for(int j = 0; j < LG; j++){

			if(root[u][j] != root[v][j]) break;

			int rt = root[u][j], pnd = -1;
			// cout << "at layer " << j << " " << root[u][j] << '\n';

			if(in[u][j] > in[v][j]){
				int uid = lower_bound(adt[rt].begin(), adt[rt].end(), make_pair(in[u][j] + 1, -1)) - adt[rt].begin();
				pnd = adt[rt][uid - 1].se;
			}else{
				int uid = lower_bound(adt[rt].begin(), adt[rt].end(), make_pair(in[v][j] + 1, -1)) - adt[rt].begin();
				pnd = adt[rt][uid - 1].se;
			}

			dep[rt].erase(make_pair(seg[j].query(1, 1, N, in[pnd][j], fn[pnd][j]), in[pnd][j]));
			if(in[u][j] < in[v][j]) seg[j].upd(1, 1, N, in[v][j], fn[v][j], df);
			else seg[j].upd(1, 1, N, in[u][j], fn[u][j], df);
			dep[rt].insert(make_pair(seg[j].query(1, 1, N, in[pnd][j], fn[pnd][j]), in[pnd][j]));

			{
				ll ans = 0;
				set<pli>::iterator it = dep[rt].end(); 

				if(it != dep[rt].begin()){
					it--;
					ans += (*it).fi;
				}

				if(it != dep[rt].begin()){
					it--;
					ans += (*it).fi;
				}

				superseg.upd(rt, ans);
			}
		}

		edges[idx].se = nw;

		last = superseg.que(1, N);
		cout << last << '\n';
	}
}

Compilation message

diameter.cpp: In member function 'void segtree::upd(int, int, int, int, int, long long int)':
diameter.cpp:124:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |    int mid = l + r >> 1;
      |              ~~^~~
diameter.cpp: In member function 'long long int segtree::query(int, int, int, int, int)':
diameter.cpp:137:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |    int mid = l + r >> 1;
      |              ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 6 ms 9844 KB Output is correct
7 Correct 6 ms 9992 KB Output is correct
8 Correct 7 ms 9912 KB Output is correct
9 Correct 6 ms 9896 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 8 ms 9812 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 6 ms 9860 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 7 ms 9900 KB Output is correct
16 Correct 6 ms 9940 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 7 ms 9952 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 6 ms 9844 KB Output is correct
7 Correct 6 ms 9992 KB Output is correct
8 Correct 7 ms 9912 KB Output is correct
9 Correct 6 ms 9896 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 8 ms 9812 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 6 ms 9860 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 7 ms 9900 KB Output is correct
16 Correct 6 ms 9940 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 7 ms 9952 KB Output is correct
19 Correct 24 ms 10648 KB Output is correct
20 Correct 26 ms 10644 KB Output is correct
21 Correct 33 ms 10640 KB Output is correct
22 Correct 35 ms 10756 KB Output is correct
23 Correct 51 ms 14096 KB Output is correct
24 Correct 72 ms 14616 KB Output is correct
25 Correct 77 ms 14920 KB Output is correct
26 Correct 68 ms 15528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 18 ms 9916 KB Output is correct
5 Correct 70 ms 10192 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 8 ms 9940 KB Output is correct
10 Correct 24 ms 10128 KB Output is correct
11 Correct 98 ms 10396 KB Output is correct
12 Correct 11 ms 12152 KB Output is correct
13 Correct 11 ms 12124 KB Output is correct
14 Correct 13 ms 12244 KB Output is correct
15 Correct 43 ms 12364 KB Output is correct
16 Correct 139 ms 12816 KB Output is correct
17 Correct 134 ms 55800 KB Output is correct
18 Correct 144 ms 55724 KB Output is correct
19 Correct 156 ms 55924 KB Output is correct
20 Correct 216 ms 55928 KB Output is correct
21 Correct 416 ms 56356 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10580 KB Output is correct
2 Correct 41 ms 10744 KB Output is correct
3 Correct 176 ms 10968 KB Output is correct
4 Correct 382 ms 11372 KB Output is correct
5 Correct 43 ms 19976 KB Output is correct
6 Correct 100 ms 20028 KB Output is correct
7 Correct 334 ms 20268 KB Output is correct
8 Correct 601 ms 20704 KB Output is correct
9 Correct 246 ms 58620 KB Output is correct
10 Correct 357 ms 58668 KB Output is correct
11 Correct 673 ms 58856 KB Output is correct
12 Correct 1182 ms 59208 KB Output is correct
13 Correct 530 ms 110844 KB Output is correct
14 Correct 628 ms 110564 KB Output is correct
15 Correct 1093 ms 110956 KB Output is correct
16 Correct 1654 ms 111056 KB Output is correct
17 Correct 2704 ms 111292 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2715 ms 98832 KB Output is correct
2 Correct 2759 ms 101236 KB Output is correct
3 Correct 2609 ms 100572 KB Output is correct
4 Correct 2673 ms 101356 KB Output is correct
5 Correct 2771 ms 98100 KB Output is correct
6 Correct 2283 ms 82976 KB Output is correct
7 Correct 3881 ms 116616 KB Output is correct
8 Correct 3888 ms 116744 KB Output is correct
9 Correct 3995 ms 116908 KB Output is correct
10 Correct 3763 ms 116728 KB Output is correct
11 Correct 3439 ms 112828 KB Output is correct
12 Correct 3016 ms 91804 KB Output is correct
13 Correct 3823 ms 125748 KB Output is correct
14 Correct 3923 ms 125720 KB Output is correct
15 Correct 3997 ms 125744 KB Output is correct
16 Correct 3816 ms 125356 KB Output is correct
17 Correct 3820 ms 120456 KB Output is correct
18 Correct 3269 ms 94544 KB Output is correct
19 Correct 4078 ms 125720 KB Output is correct
20 Correct 4101 ms 125640 KB Output is correct
21 Correct 3933 ms 125716 KB Output is correct
22 Correct 4038 ms 125332 KB Output is correct
23 Correct 3649 ms 120576 KB Output is correct
24 Correct 3166 ms 94712 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9744 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 7 ms 9812 KB Output is correct
5 Correct 6 ms 9772 KB Output is correct
6 Correct 6 ms 9844 KB Output is correct
7 Correct 6 ms 9992 KB Output is correct
8 Correct 7 ms 9912 KB Output is correct
9 Correct 6 ms 9896 KB Output is correct
10 Correct 7 ms 9812 KB Output is correct
11 Correct 8 ms 9812 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 6 ms 9860 KB Output is correct
14 Correct 6 ms 9940 KB Output is correct
15 Correct 7 ms 9900 KB Output is correct
16 Correct 6 ms 9940 KB Output is correct
17 Correct 6 ms 9940 KB Output is correct
18 Correct 7 ms 9952 KB Output is correct
19 Correct 24 ms 10648 KB Output is correct
20 Correct 26 ms 10644 KB Output is correct
21 Correct 33 ms 10640 KB Output is correct
22 Correct 35 ms 10756 KB Output is correct
23 Correct 51 ms 14096 KB Output is correct
24 Correct 72 ms 14616 KB Output is correct
25 Correct 77 ms 14920 KB Output is correct
26 Correct 68 ms 15528 KB Output is correct
27 Correct 5 ms 9812 KB Output is correct
28 Correct 5 ms 9812 KB Output is correct
29 Correct 6 ms 9812 KB Output is correct
30 Correct 18 ms 9916 KB Output is correct
31 Correct 70 ms 10192 KB Output is correct
32 Correct 5 ms 9812 KB Output is correct
33 Correct 6 ms 9940 KB Output is correct
34 Correct 6 ms 9940 KB Output is correct
35 Correct 8 ms 9940 KB Output is correct
36 Correct 24 ms 10128 KB Output is correct
37 Correct 98 ms 10396 KB Output is correct
38 Correct 11 ms 12152 KB Output is correct
39 Correct 11 ms 12124 KB Output is correct
40 Correct 13 ms 12244 KB Output is correct
41 Correct 43 ms 12364 KB Output is correct
42 Correct 139 ms 12816 KB Output is correct
43 Correct 134 ms 55800 KB Output is correct
44 Correct 144 ms 55724 KB Output is correct
45 Correct 156 ms 55924 KB Output is correct
46 Correct 216 ms 55928 KB Output is correct
47 Correct 416 ms 56356 KB Output is correct
48 Correct 13 ms 10580 KB Output is correct
49 Correct 41 ms 10744 KB Output is correct
50 Correct 176 ms 10968 KB Output is correct
51 Correct 382 ms 11372 KB Output is correct
52 Correct 43 ms 19976 KB Output is correct
53 Correct 100 ms 20028 KB Output is correct
54 Correct 334 ms 20268 KB Output is correct
55 Correct 601 ms 20704 KB Output is correct
56 Correct 246 ms 58620 KB Output is correct
57 Correct 357 ms 58668 KB Output is correct
58 Correct 673 ms 58856 KB Output is correct
59 Correct 1182 ms 59208 KB Output is correct
60 Correct 530 ms 110844 KB Output is correct
61 Correct 628 ms 110564 KB Output is correct
62 Correct 1093 ms 110956 KB Output is correct
63 Correct 1654 ms 111056 KB Output is correct
64 Correct 2704 ms 111292 KB Output is correct
65 Correct 2715 ms 98832 KB Output is correct
66 Correct 2759 ms 101236 KB Output is correct
67 Correct 2609 ms 100572 KB Output is correct
68 Correct 2673 ms 101356 KB Output is correct
69 Correct 2771 ms 98100 KB Output is correct
70 Correct 2283 ms 82976 KB Output is correct
71 Correct 3881 ms 116616 KB Output is correct
72 Correct 3888 ms 116744 KB Output is correct
73 Correct 3995 ms 116908 KB Output is correct
74 Correct 3763 ms 116728 KB Output is correct
75 Correct 3439 ms 112828 KB Output is correct
76 Correct 3016 ms 91804 KB Output is correct
77 Correct 3823 ms 125748 KB Output is correct
78 Correct 3923 ms 125720 KB Output is correct
79 Correct 3997 ms 125744 KB Output is correct
80 Correct 3816 ms 125356 KB Output is correct
81 Correct 3820 ms 120456 KB Output is correct
82 Correct 3269 ms 94544 KB Output is correct
83 Correct 4078 ms 125720 KB Output is correct
84 Correct 4101 ms 125640 KB Output is correct
85 Correct 3933 ms 125716 KB Output is correct
86 Correct 4038 ms 125332 KB Output is correct
87 Correct 3649 ms 120576 KB Output is correct
88 Correct 3166 ms 94712 KB Output is correct
89 Correct 3126 ms 102880 KB Output is correct
90 Correct 3113 ms 108820 KB Output is correct
91 Correct 4159 ms 116576 KB Output is correct
92 Correct 4168 ms 118372 KB Output is correct
93 Correct 3820 ms 122512 KB Output is correct
94 Correct 3785 ms 122680 KB Output is correct
95 Correct 3911 ms 125640 KB Output is correct
96 Correct 4622 ms 124468 KB Output is correct
97 Correct 4555 ms 125560 KB Output is correct
98 Correct 4887 ms 127876 KB Output is correct
99 Correct 3953 ms 125280 KB Output is correct
100 Correct 3815 ms 125232 KB Output is correct