oj.uz

Submission #1084316

# Submission time Handle Problem Language Result Execution time Memory
1084316 2024-09-05T20:30:49 Z xnqs Birthday gift (IZhO18_treearray) C++17
100 / 100
 547 ms 82568 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>

int gs, x, q;
std::vector<std::vector<int>> adj_list;
int arr[200005];
int up[18][200005];
int depth[200005];
std::set<int> occurences1[200005]; // occurences of node i in arr
std::set<int> occurences2[200005]; // occurences of lca of any two consecutive nodes in arr

void dfs(int k, int p) {
	depth[k] = depth[p]+1;
	up[0][k] = p;
	for (int l = 1; l < 18; l++) {
		up[l][k] = up[l-1][up[l-1][k]];
	}

	for (const auto& i : adj_list[k]) {
		if (i!=p) {
			dfs(i,k);
		}
	}
}

int get_kth_ancestor(int node, int k) {
	while (k) {
		int lvl = 31-__builtin_clz(k);
		node = up[lvl][node];
		k ^= (1<<lvl);
	}
	return node;
}

int get_lca(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	b = get_kth_ancestor(b,depth[b]-depth[a]);

	for (int lvl = 17; a != b;) {
		while (lvl-1>=0&&up[lvl][a]==up[lvl][b]) {
			--lvl;
		}

		a = up[lvl][a];
		b = up[lvl][b];
	}

	return a;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> x >> q;
	adj_list.resize(gs+1);
	for (int i = 0, a, b; i < gs-1; i++) {
		std::cin >> a >> b;
		adj_list[a].emplace_back(b);
		adj_list[b].emplace_back(a);
	}

	dfs(1,0);

	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		occurences1[arr[i]].emplace(i);
	}
	for (int i = 1; i+1 <= x; i++) {
		occurences2[get_lca(arr[i],arr[i+1])].emplace(i);
	}

	while (q--) {
		int op;
		std::cin >> op;
		if (op==1) {
			int pos, val;
			std::cin >> pos >> val;

			occurences1[arr[pos]].erase(pos);
			if (pos-1>=1) {
				occurences2[get_lca(arr[pos-1],arr[pos])].erase(pos-1);
			}
			if (pos+1<=x) {
				occurences2[get_lca(arr[pos],arr[pos+1])].erase(pos);
			}

			arr[pos] = val;
			occurences1[arr[pos]].emplace(pos);
			if (pos-1>=1) {
				occurences2[get_lca(arr[pos-1],arr[pos])].emplace(pos-1);
			}
			if (pos+1<=x) {
				occurences2[get_lca(arr[pos],arr[pos+1])].emplace(pos);
			}
		}
		else {
			int l, r, k;
			std::cin >> l >> r >> k;

			// if k itself pops up in [l, r]
			auto it = occurences1[k].lower_bound(l);
			if (it!=occurences1[k].end()&&*it<=r) {
				std::cout << (*it) << " " << (*it) << "\n";
				continue;
			}

			// if two consecutive occurences with lca k happen in [l, r]
			it = occurences2[k].lower_bound(l);
			if (it!=occurences2[k].end()&&(*it+1)<=r) {
				std::cout << (*it) << " " << (*it+1) << "\n";
				continue;
			}

			std::cout << "-1 -1\n";
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB n=5
2 Correct 8 ms 19248 KB n=100
3 Correct 8 ms 19292 KB n=100
4 Correct 7 ms 19292 KB n=100
5 Correct 8 ms 19372 KB n=100
6 Correct 8 ms 19288 KB n=100
7 Correct 9 ms 19292 KB n=100
8 Correct 8 ms 19292 KB n=100
9 Correct 8 ms 19292 KB n=100
10 Correct 11 ms 19288 KB n=100
11 Correct 9 ms 19292 KB n=100
12 Correct 11 ms 19292 KB n=100
13 Correct 8 ms 19292 KB n=100
14 Correct 9 ms 19292 KB n=100
15 Correct 8 ms 19292 KB n=100
16 Correct 9 ms 19292 KB n=100
17 Correct 8 ms 19292 KB n=100
18 Correct 7 ms 19288 KB n=100
19 Correct 8 ms 19288 KB n=100
20 Correct 7 ms 19292 KB n=100
21 Correct 12 ms 19292 KB n=100
22 Correct 9 ms 19292 KB n=100
23 Correct 8 ms 19292 KB n=100
24 Correct 8 ms 19376 KB n=100
25 Correct 8 ms 19288 KB n=100
26 Correct 9 ms 19292 KB n=12
27 Correct 11 ms 19292 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB n=5
2 Correct 8 ms 19248 KB n=100
3 Correct 8 ms 19292 KB n=100
4 Correct 7 ms 19292 KB n=100
5 Correct 8 ms 19372 KB n=100
6 Correct 8 ms 19288 KB n=100
7 Correct 9 ms 19292 KB n=100
8 Correct 8 ms 19292 KB n=100
9 Correct 8 ms 19292 KB n=100
10 Correct 11 ms 19288 KB n=100
11 Correct 9 ms 19292 KB n=100
12 Correct 11 ms 19292 KB n=100
13 Correct 8 ms 19292 KB n=100
14 Correct 9 ms 19292 KB n=100
15 Correct 8 ms 19292 KB n=100
16 Correct 9 ms 19292 KB n=100
17 Correct 8 ms 19292 KB n=100
18 Correct 7 ms 19288 KB n=100
19 Correct 8 ms 19288 KB n=100
20 Correct 7 ms 19292 KB n=100
21 Correct 12 ms 19292 KB n=100
22 Correct 9 ms 19292 KB n=100
23 Correct 8 ms 19292 KB n=100
24 Correct 8 ms 19376 KB n=100
25 Correct 8 ms 19288 KB n=100
26 Correct 9 ms 19292 KB n=12
27 Correct 11 ms 19292 KB n=100
28 Correct 9 ms 19292 KB n=500
29 Correct 12 ms 19288 KB n=500
30 Correct 9 ms 19292 KB n=500
31 Correct 8 ms 19292 KB n=500
32 Correct 9 ms 19292 KB n=500
33 Correct 9 ms 19440 KB n=500
34 Correct 8 ms 19288 KB n=500
35 Correct 9 ms 19292 KB n=500
36 Correct 8 ms 19292 KB n=500
37 Correct 10 ms 19452 KB n=500
38 Correct 7 ms 19292 KB n=500
39 Correct 8 ms 19288 KB n=500
40 Correct 8 ms 19292 KB n=500
41 Correct 12 ms 19288 KB n=500
42 Correct 8 ms 19292 KB n=500
43 Correct 8 ms 19288 KB n=500
44 Correct 9 ms 19292 KB n=500
45 Correct 8 ms 19292 KB n=500
46 Correct 8 ms 19288 KB n=500
47 Correct 10 ms 19292 KB n=500
48 Correct 8 ms 19288 KB n=500
49 Correct 12 ms 19288 KB n=500
50 Correct 8 ms 19288 KB n=500
51 Correct 8 ms 19292 KB n=500
52 Correct 8 ms 19352 KB n=500
53 Correct 9 ms 19292 KB n=500
54 Correct 8 ms 19292 KB n=500
55 Correct 8 ms 19284 KB n=278
56 Correct 8 ms 19288 KB n=500
57 Correct 9 ms 19292 KB n=500
58 Correct 12 ms 19292 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB n=5
2 Correct 8 ms 19248 KB n=100
3 Correct 8 ms 19292 KB n=100
4 Correct 7 ms 19292 KB n=100
5 Correct 8 ms 19372 KB n=100
6 Correct 8 ms 19288 KB n=100
7 Correct 9 ms 19292 KB n=100
8 Correct 8 ms 19292 KB n=100
9 Correct 8 ms 19292 KB n=100
10 Correct 11 ms 19288 KB n=100
11 Correct 9 ms 19292 KB n=100
12 Correct 11 ms 19292 KB n=100
13 Correct 8 ms 19292 KB n=100
14 Correct 9 ms 19292 KB n=100
15 Correct 8 ms 19292 KB n=100
16 Correct 9 ms 19292 KB n=100
17 Correct 8 ms 19292 KB n=100
18 Correct 7 ms 19288 KB n=100
19 Correct 8 ms 19288 KB n=100
20 Correct 7 ms 19292 KB n=100
21 Correct 12 ms 19292 KB n=100
22 Correct 9 ms 19292 KB n=100
23 Correct 8 ms 19292 KB n=100
24 Correct 8 ms 19376 KB n=100
25 Correct 8 ms 19288 KB n=100
26 Correct 9 ms 19292 KB n=12
27 Correct 11 ms 19292 KB n=100
28 Correct 9 ms 19292 KB n=500
29 Correct 12 ms 19288 KB n=500
30 Correct 9 ms 19292 KB n=500
31 Correct 8 ms 19292 KB n=500
32 Correct 9 ms 19292 KB n=500
33 Correct 9 ms 19440 KB n=500
34 Correct 8 ms 19288 KB n=500
35 Correct 9 ms 19292 KB n=500
36 Correct 8 ms 19292 KB n=500
37 Correct 10 ms 19452 KB n=500
38 Correct 7 ms 19292 KB n=500
39 Correct 8 ms 19288 KB n=500
40 Correct 8 ms 19292 KB n=500
41 Correct 12 ms 19288 KB n=500
42 Correct 8 ms 19292 KB n=500
43 Correct 8 ms 19288 KB n=500
44 Correct 9 ms 19292 KB n=500
45 Correct 8 ms 19292 KB n=500
46 Correct 8 ms 19288 KB n=500
47 Correct 10 ms 19292 KB n=500
48 Correct 8 ms 19288 KB n=500
49 Correct 12 ms 19288 KB n=500
50 Correct 8 ms 19288 KB n=500
51 Correct 8 ms 19292 KB n=500
52 Correct 8 ms 19352 KB n=500
53 Correct 9 ms 19292 KB n=500
54 Correct 8 ms 19292 KB n=500
55 Correct 8 ms 19284 KB n=278
56 Correct 8 ms 19288 KB n=500
57 Correct 9 ms 19292 KB n=500
58 Correct 12 ms 19292 KB n=500
59 Correct 10 ms 19800 KB n=2000
60 Correct 10 ms 19804 KB n=2000
61 Correct 9 ms 19804 KB n=2000
62 Correct 9 ms 19804 KB n=2000
63 Correct 10 ms 19804 KB n=2000
64 Correct 14 ms 19800 KB n=2000
65 Correct 10 ms 19804 KB n=2000
66 Correct 15 ms 19804 KB n=2000
67 Correct 10 ms 19696 KB n=2000
68 Correct 9 ms 19800 KB n=2000
69 Correct 9 ms 19804 KB n=2000
70 Correct 10 ms 19804 KB n=2000
71 Correct 9 ms 19804 KB n=2000
72 Correct 13 ms 19804 KB n=2000
73 Correct 10 ms 19800 KB n=2000
74 Correct 11 ms 19804 KB n=1844
75 Correct 9 ms 19800 KB n=2000
76 Correct 10 ms 19804 KB n=2000
77 Correct 11 ms 19804 KB n=2000
78 Correct 10 ms 19804 KB n=2000
79 Correct 11 ms 19800 KB n=2000
80 Correct 10 ms 19804 KB n=2000
81 Correct 10 ms 19764 KB n=2000
82 Correct 10 ms 19800 KB n=2000
83 Correct 11 ms 19800 KB n=2000
84 Correct 10 ms 19800 KB n=2000
85 Correct 10 ms 19804 KB n=2000
86 Correct 10 ms 19800 KB n=2000
87 Correct 9 ms 19804 KB n=2000
88 Correct 14 ms 20060 KB n=2000
89 Correct 10 ms 19804 KB n=2000
90 Correct 10 ms 19804 KB n=2000
91 Correct 10 ms 19804 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19292 KB n=5
2 Correct 8 ms 19248 KB n=100
3 Correct 8 ms 19292 KB n=100
4 Correct 7 ms 19292 KB n=100
5 Correct 8 ms 19372 KB n=100
6 Correct 8 ms 19288 KB n=100
7 Correct 9 ms 19292 KB n=100
8 Correct 8 ms 19292 KB n=100
9 Correct 8 ms 19292 KB n=100
10 Correct 11 ms 19288 KB n=100
11 Correct 9 ms 19292 KB n=100
12 Correct 11 ms 19292 KB n=100
13 Correct 8 ms 19292 KB n=100
14 Correct 9 ms 19292 KB n=100
15 Correct 8 ms 19292 KB n=100
16 Correct 9 ms 19292 KB n=100
17 Correct 8 ms 19292 KB n=100
18 Correct 7 ms 19288 KB n=100
19 Correct 8 ms 19288 KB n=100
20 Correct 7 ms 19292 KB n=100
21 Correct 12 ms 19292 KB n=100
22 Correct 9 ms 19292 KB n=100
23 Correct 8 ms 19292 KB n=100
24 Correct 8 ms 19376 KB n=100
25 Correct 8 ms 19288 KB n=100
26 Correct 9 ms 19292 KB n=12
27 Correct 11 ms 19292 KB n=100
28 Correct 9 ms 19292 KB n=500
29 Correct 12 ms 19288 KB n=500
30 Correct 9 ms 19292 KB n=500
31 Correct 8 ms 19292 KB n=500
32 Correct 9 ms 19292 KB n=500
33 Correct 9 ms 19440 KB n=500
34 Correct 8 ms 19288 KB n=500
35 Correct 9 ms 19292 KB n=500
36 Correct 8 ms 19292 KB n=500
37 Correct 10 ms 19452 KB n=500
38 Correct 7 ms 19292 KB n=500
39 Correct 8 ms 19288 KB n=500
40 Correct 8 ms 19292 KB n=500
41 Correct 12 ms 19288 KB n=500
42 Correct 8 ms 19292 KB n=500
43 Correct 8 ms 19288 KB n=500
44 Correct 9 ms 19292 KB n=500
45 Correct 8 ms 19292 KB n=500
46 Correct 8 ms 19288 KB n=500
47 Correct 10 ms 19292 KB n=500
48 Correct 8 ms 19288 KB n=500
49 Correct 12 ms 19288 KB n=500
50 Correct 8 ms 19288 KB n=500
51 Correct 8 ms 19292 KB n=500
52 Correct 8 ms 19352 KB n=500
53 Correct 9 ms 19292 KB n=500
54 Correct 8 ms 19292 KB n=500
55 Correct 8 ms 19284 KB n=278
56 Correct 8 ms 19288 KB n=500
57 Correct 9 ms 19292 KB n=500
58 Correct 12 ms 19292 KB n=500
59 Correct 10 ms 19800 KB n=2000
60 Correct 10 ms 19804 KB n=2000
61 Correct 9 ms 19804 KB n=2000
62 Correct 9 ms 19804 KB n=2000
63 Correct 10 ms 19804 KB n=2000
64 Correct 14 ms 19800 KB n=2000
65 Correct 10 ms 19804 KB n=2000
66 Correct 15 ms 19804 KB n=2000
67 Correct 10 ms 19696 KB n=2000
68 Correct 9 ms 19800 KB n=2000
69 Correct 9 ms 19804 KB n=2000
70 Correct 10 ms 19804 KB n=2000
71 Correct 9 ms 19804 KB n=2000
72 Correct 13 ms 19804 KB n=2000
73 Correct 10 ms 19800 KB n=2000
74 Correct 11 ms 19804 KB n=1844
75 Correct 9 ms 19800 KB n=2000
76 Correct 10 ms 19804 KB n=2000
77 Correct 11 ms 19804 KB n=2000
78 Correct 10 ms 19804 KB n=2000
79 Correct 11 ms 19800 KB n=2000
80 Correct 10 ms 19804 KB n=2000
81 Correct 10 ms 19764 KB n=2000
82 Correct 10 ms 19800 KB n=2000
83 Correct 11 ms 19800 KB n=2000
84 Correct 10 ms 19800 KB n=2000
85 Correct 10 ms 19804 KB n=2000
86 Correct 10 ms 19800 KB n=2000
87 Correct 9 ms 19804 KB n=2000
88 Correct 14 ms 20060 KB n=2000
89 Correct 10 ms 19804 KB n=2000
90 Correct 10 ms 19804 KB n=2000
91 Correct 10 ms 19804 KB n=2000
92 Correct 444 ms 72896 KB n=200000
93 Correct 509 ms 77856 KB n=200000
94 Correct 445 ms 81232 KB n=200000
95 Correct 437 ms 72680 KB n=200000
96 Correct 407 ms 72900 KB n=200000
97 Correct 499 ms 77140 KB n=200000
98 Correct 417 ms 72860 KB n=200000
99 Correct 529 ms 73044 KB n=200000
100 Correct 433 ms 72924 KB n=200000
101 Correct 453 ms 82568 KB n=200000
102 Correct 252 ms 74064 KB n=200000
103 Correct 241 ms 74068 KB n=200000
104 Correct 286 ms 74076 KB n=200000
105 Correct 270 ms 74416 KB n=200000
106 Correct 254 ms 74324 KB n=200000
107 Correct 264 ms 74324 KB n=200000
108 Correct 474 ms 73052 KB n=200000
109 Correct 491 ms 73040 KB n=200000
110 Correct 501 ms 73000 KB n=200000
111 Correct 440 ms 72268 KB n=200000
112 Correct 459 ms 81480 KB n=200000
113 Correct 501 ms 77248 KB n=200000
114 Correct 432 ms 72648 KB n=200000
115 Correct 547 ms 74996 KB n=200000
116 Correct 423 ms 73008 KB n=200000
117 Correct 427 ms 81972 KB n=200000
118 Correct 519 ms 75860 KB n=200000
119 Correct 398 ms 72908 KB n=200000
120 Correct 395 ms 81488 KB n=200000
121 Correct 437 ms 81556 KB n=200000
122 Correct 420 ms 81748 KB n=200000
123 Correct 251 ms 74320 KB n=200000
124 Correct 95 ms 34384 KB n=25264