oj.uz

Submission #543231

# Submission time Handle Problem Language Result Execution time Memory
543231 2022-03-29T21:42:20 Z MarcosPauloEvers Birthday gift (IZhO18_treearray) C++17
100 / 100
 935 ms 68624 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10, MAXK = 18;
int n, m;
set<int> pos[MAXN], pos_lca[MAXN];

vector<int> adj[MAXN];
int lift[MAXN][MAXK], depth[MAXN];
int arr[MAXN], arr_lca[MAXN];

void init_lca()
{
	memset(lift, -1, sizeof lift);
	queue<int> que;
	que.push(1);
	lift[1][0] = 1;
	depth[1] = 0;
	while(!que.empty())
	{
		int v = que.front(); que.pop();

		for(int u: adj[v])
			if(lift[u][0] == -1)
				lift[u][0] = v, depth[u] = depth[v] + 1, que.push(u);
	}

	for(int k = 1; k < MAXK; k++)
		for(int i = 1; i <= n; i++)
			lift[i][k] = lift[lift[i][k-1]][k-1];
}

int get_lca(int u, int v)
{
	if(depth[u] < depth[v]) swap(u, v);

	for(int k = MAXK - 1; k >= 0; k--)
		if(depth[u] - (1 << k) >= depth[v])
			u = lift[u][k];

	if(u == v) return u;

	for(int k = MAXK - 1; k >= 0; k--)
		if(lift[u][k] != lift[v][k])
			u = lift[u][k], v = lift[v][k];

	return lift[u][0];
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int q;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;

		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	init_lca();
	for(int i = 1; i <= m; i++)
	{
		cin >> arr[i];

		pos[arr[i]].insert(i);
	}
	
	for(int i = 1; i < m; i++)
		pos_lca[get_lca(arr[i], arr[i+1])].insert(i);

	while(q--)
	{
		int op; cin >> op;

		if(op == 1)
		{
			int i, v; cin >> i >> v;

			if(i > 1)
			{
				pos_lca[get_lca(arr[i - 1], arr[i])].erase(i - 1);
				pos_lca[get_lca(arr[i - 1], v)].insert(i - 1);
			}

			if(i < m)
			{
				pos_lca[get_lca(arr[i], arr[i + 1])].erase(i);
				pos_lca[get_lca(v, arr[i + 1])].insert(i);
			}

			pos[arr[i]].erase(i);
			pos[v].insert(i);

			arr[i] = v;
		} else
		{
			int l, r, v; cin >> l >> r >> v;

			auto it1 = pos[v].lower_bound(l);
			auto it2 = pos_lca[v].lower_bound(l);

			if(it1 != pos[v].end() && *it1 <= r)
				cout << *it1 << " " << *it1 << "\n";
			else if(it2 != pos_lca[v].end() && *it2 < r)
				cout << *it2 << " " << *it2 + 1 << "\n";
			else
				cout << -1 << " " << -1 << "\n";
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37816 KB n=5
2 Correct 19 ms 37892 KB n=100
3 Correct 17 ms 37844 KB n=100
4 Correct 17 ms 37812 KB n=100
5 Correct 17 ms 37892 KB n=100
6 Correct 17 ms 37844 KB n=100
7 Correct 16 ms 37896 KB n=100
8 Correct 17 ms 37844 KB n=100
9 Correct 17 ms 37844 KB n=100
10 Correct 20 ms 37908 KB n=100
11 Correct 17 ms 37844 KB n=100
12 Correct 18 ms 37928 KB n=100
13 Correct 17 ms 37848 KB n=100
14 Correct 17 ms 37844 KB n=100
15 Correct 18 ms 37888 KB n=100
16 Correct 19 ms 37844 KB n=100
17 Correct 18 ms 37844 KB n=100
18 Correct 17 ms 37844 KB n=100
19 Correct 17 ms 37844 KB n=100
20 Correct 17 ms 37900 KB n=100
21 Correct 19 ms 37976 KB n=100
22 Correct 17 ms 37820 KB n=100
23 Correct 17 ms 37844 KB n=100
24 Correct 17 ms 37904 KB n=100
25 Correct 17 ms 37856 KB n=100
26 Correct 17 ms 37892 KB n=12
27 Correct 17 ms 37892 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37816 KB n=5
2 Correct 19 ms 37892 KB n=100
3 Correct 17 ms 37844 KB n=100
4 Correct 17 ms 37812 KB n=100
5 Correct 17 ms 37892 KB n=100
6 Correct 17 ms 37844 KB n=100
7 Correct 16 ms 37896 KB n=100
8 Correct 17 ms 37844 KB n=100
9 Correct 17 ms 37844 KB n=100
10 Correct 20 ms 37908 KB n=100
11 Correct 17 ms 37844 KB n=100
12 Correct 18 ms 37928 KB n=100
13 Correct 17 ms 37848 KB n=100
14 Correct 17 ms 37844 KB n=100
15 Correct 18 ms 37888 KB n=100
16 Correct 19 ms 37844 KB n=100
17 Correct 18 ms 37844 KB n=100
18 Correct 17 ms 37844 KB n=100
19 Correct 17 ms 37844 KB n=100
20 Correct 17 ms 37900 KB n=100
21 Correct 19 ms 37976 KB n=100
22 Correct 17 ms 37820 KB n=100
23 Correct 17 ms 37844 KB n=100
24 Correct 17 ms 37904 KB n=100
25 Correct 17 ms 37856 KB n=100
26 Correct 17 ms 37892 KB n=12
27 Correct 17 ms 37892 KB n=100
28 Correct 17 ms 37972 KB n=500
29 Correct 20 ms 37928 KB n=500
30 Correct 18 ms 37908 KB n=500
31 Correct 18 ms 37908 KB n=500
32 Correct 17 ms 37900 KB n=500
33 Correct 19 ms 37972 KB n=500
34 Correct 18 ms 37892 KB n=500
35 Correct 18 ms 37912 KB n=500
36 Correct 18 ms 37900 KB n=500
37 Correct 17 ms 37960 KB n=500
38 Correct 17 ms 37972 KB n=500
39 Correct 18 ms 37972 KB n=500
40 Correct 18 ms 37912 KB n=500
41 Correct 19 ms 37908 KB n=500
42 Correct 18 ms 37972 KB n=500
43 Correct 17 ms 37972 KB n=500
44 Correct 17 ms 37972 KB n=500
45 Correct 17 ms 37904 KB n=500
46 Correct 18 ms 38004 KB n=500
47 Correct 18 ms 37972 KB n=500
48 Correct 17 ms 38004 KB n=500
49 Correct 17 ms 37904 KB n=500
50 Correct 21 ms 37904 KB n=500
51 Correct 18 ms 37908 KB n=500
52 Correct 18 ms 37900 KB n=500
53 Correct 17 ms 37904 KB n=500
54 Correct 18 ms 37896 KB n=500
55 Correct 17 ms 37896 KB n=278
56 Correct 17 ms 37972 KB n=500
57 Correct 19 ms 38004 KB n=500
58 Correct 18 ms 37972 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37816 KB n=5
2 Correct 19 ms 37892 KB n=100
3 Correct 17 ms 37844 KB n=100
4 Correct 17 ms 37812 KB n=100
5 Correct 17 ms 37892 KB n=100
6 Correct 17 ms 37844 KB n=100
7 Correct 16 ms 37896 KB n=100
8 Correct 17 ms 37844 KB n=100
9 Correct 17 ms 37844 KB n=100
10 Correct 20 ms 37908 KB n=100
11 Correct 17 ms 37844 KB n=100
12 Correct 18 ms 37928 KB n=100
13 Correct 17 ms 37848 KB n=100
14 Correct 17 ms 37844 KB n=100
15 Correct 18 ms 37888 KB n=100
16 Correct 19 ms 37844 KB n=100
17 Correct 18 ms 37844 KB n=100
18 Correct 17 ms 37844 KB n=100
19 Correct 17 ms 37844 KB n=100
20 Correct 17 ms 37900 KB n=100
21 Correct 19 ms 37976 KB n=100
22 Correct 17 ms 37820 KB n=100
23 Correct 17 ms 37844 KB n=100
24 Correct 17 ms 37904 KB n=100
25 Correct 17 ms 37856 KB n=100
26 Correct 17 ms 37892 KB n=12
27 Correct 17 ms 37892 KB n=100
28 Correct 17 ms 37972 KB n=500
29 Correct 20 ms 37928 KB n=500
30 Correct 18 ms 37908 KB n=500
31 Correct 18 ms 37908 KB n=500
32 Correct 17 ms 37900 KB n=500
33 Correct 19 ms 37972 KB n=500
34 Correct 18 ms 37892 KB n=500
35 Correct 18 ms 37912 KB n=500
36 Correct 18 ms 37900 KB n=500
37 Correct 17 ms 37960 KB n=500
38 Correct 17 ms 37972 KB n=500
39 Correct 18 ms 37972 KB n=500
40 Correct 18 ms 37912 KB n=500
41 Correct 19 ms 37908 KB n=500
42 Correct 18 ms 37972 KB n=500
43 Correct 17 ms 37972 KB n=500
44 Correct 17 ms 37972 KB n=500
45 Correct 17 ms 37904 KB n=500
46 Correct 18 ms 38004 KB n=500
47 Correct 18 ms 37972 KB n=500
48 Correct 17 ms 38004 KB n=500
49 Correct 17 ms 37904 KB n=500
50 Correct 21 ms 37904 KB n=500
51 Correct 18 ms 37908 KB n=500
52 Correct 18 ms 37900 KB n=500
53 Correct 17 ms 37904 KB n=500
54 Correct 18 ms 37896 KB n=500
55 Correct 17 ms 37896 KB n=278
56 Correct 17 ms 37972 KB n=500
57 Correct 19 ms 38004 KB n=500
58 Correct 18 ms 37972 KB n=500
59 Correct 19 ms 38228 KB n=2000
60 Correct 19 ms 38152 KB n=2000
61 Correct 21 ms 38156 KB n=2000
62 Correct 20 ms 38220 KB n=2000
63 Correct 20 ms 38208 KB n=2000
64 Correct 20 ms 38236 KB n=2000
65 Correct 21 ms 38164 KB n=2000
66 Correct 20 ms 38240 KB n=2000
67 Correct 20 ms 38168 KB n=2000
68 Correct 19 ms 38160 KB n=2000
69 Correct 19 ms 38228 KB n=2000
70 Correct 18 ms 38228 KB n=2000
71 Correct 19 ms 38240 KB n=2000
72 Correct 18 ms 38128 KB n=2000
73 Correct 19 ms 38252 KB n=2000
74 Correct 19 ms 38156 KB n=1844
75 Correct 21 ms 38156 KB n=2000
76 Correct 19 ms 38164 KB n=2000
77 Correct 20 ms 38156 KB n=2000
78 Correct 20 ms 38228 KB n=2000
79 Correct 22 ms 38128 KB n=2000
80 Correct 19 ms 38124 KB n=2000
81 Correct 19 ms 38112 KB n=2000
82 Correct 19 ms 38164 KB n=2000
83 Correct 21 ms 38112 KB n=2000
84 Correct 19 ms 38212 KB n=2000
85 Correct 21 ms 38228 KB n=2000
86 Correct 19 ms 38164 KB n=2000
87 Correct 22 ms 38152 KB n=2000
88 Correct 20 ms 38164 KB n=2000
89 Correct 19 ms 38240 KB n=2000
90 Correct 19 ms 38228 KB n=2000
91 Correct 19 ms 38164 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37816 KB n=5
2 Correct 19 ms 37892 KB n=100
3 Correct 17 ms 37844 KB n=100
4 Correct 17 ms 37812 KB n=100
5 Correct 17 ms 37892 KB n=100
6 Correct 17 ms 37844 KB n=100
7 Correct 16 ms 37896 KB n=100
8 Correct 17 ms 37844 KB n=100
9 Correct 17 ms 37844 KB n=100
10 Correct 20 ms 37908 KB n=100
11 Correct 17 ms 37844 KB n=100
12 Correct 18 ms 37928 KB n=100
13 Correct 17 ms 37848 KB n=100
14 Correct 17 ms 37844 KB n=100
15 Correct 18 ms 37888 KB n=100
16 Correct 19 ms 37844 KB n=100
17 Correct 18 ms 37844 KB n=100
18 Correct 17 ms 37844 KB n=100
19 Correct 17 ms 37844 KB n=100
20 Correct 17 ms 37900 KB n=100
21 Correct 19 ms 37976 KB n=100
22 Correct 17 ms 37820 KB n=100
23 Correct 17 ms 37844 KB n=100
24 Correct 17 ms 37904 KB n=100
25 Correct 17 ms 37856 KB n=100
26 Correct 17 ms 37892 KB n=12
27 Correct 17 ms 37892 KB n=100
28 Correct 17 ms 37972 KB n=500
29 Correct 20 ms 37928 KB n=500
30 Correct 18 ms 37908 KB n=500
31 Correct 18 ms 37908 KB n=500
32 Correct 17 ms 37900 KB n=500
33 Correct 19 ms 37972 KB n=500
34 Correct 18 ms 37892 KB n=500
35 Correct 18 ms 37912 KB n=500
36 Correct 18 ms 37900 KB n=500
37 Correct 17 ms 37960 KB n=500
38 Correct 17 ms 37972 KB n=500
39 Correct 18 ms 37972 KB n=500
40 Correct 18 ms 37912 KB n=500
41 Correct 19 ms 37908 KB n=500
42 Correct 18 ms 37972 KB n=500
43 Correct 17 ms 37972 KB n=500
44 Correct 17 ms 37972 KB n=500
45 Correct 17 ms 37904 KB n=500
46 Correct 18 ms 38004 KB n=500
47 Correct 18 ms 37972 KB n=500
48 Correct 17 ms 38004 KB n=500
49 Correct 17 ms 37904 KB n=500
50 Correct 21 ms 37904 KB n=500
51 Correct 18 ms 37908 KB n=500
52 Correct 18 ms 37900 KB n=500
53 Correct 17 ms 37904 KB n=500
54 Correct 18 ms 37896 KB n=500
55 Correct 17 ms 37896 KB n=278
56 Correct 17 ms 37972 KB n=500
57 Correct 19 ms 38004 KB n=500
58 Correct 18 ms 37972 KB n=500
59 Correct 19 ms 38228 KB n=2000
60 Correct 19 ms 38152 KB n=2000
61 Correct 21 ms 38156 KB n=2000
62 Correct 20 ms 38220 KB n=2000
63 Correct 20 ms 38208 KB n=2000
64 Correct 20 ms 38236 KB n=2000
65 Correct 21 ms 38164 KB n=2000
66 Correct 20 ms 38240 KB n=2000
67 Correct 20 ms 38168 KB n=2000
68 Correct 19 ms 38160 KB n=2000
69 Correct 19 ms 38228 KB n=2000
70 Correct 18 ms 38228 KB n=2000
71 Correct 19 ms 38240 KB n=2000
72 Correct 18 ms 38128 KB n=2000
73 Correct 19 ms 38252 KB n=2000
74 Correct 19 ms 38156 KB n=1844
75 Correct 21 ms 38156 KB n=2000
76 Correct 19 ms 38164 KB n=2000
77 Correct 20 ms 38156 KB n=2000
78 Correct 20 ms 38228 KB n=2000
79 Correct 22 ms 38128 KB n=2000
80 Correct 19 ms 38124 KB n=2000
81 Correct 19 ms 38112 KB n=2000
82 Correct 19 ms 38164 KB n=2000
83 Correct 21 ms 38112 KB n=2000
84 Correct 19 ms 38212 KB n=2000
85 Correct 21 ms 38228 KB n=2000
86 Correct 19 ms 38164 KB n=2000
87 Correct 22 ms 38152 KB n=2000
88 Correct 20 ms 38164 KB n=2000
89 Correct 19 ms 38240 KB n=2000
90 Correct 19 ms 38228 KB n=2000
91 Correct 19 ms 38164 KB n=2000
92 Correct 582 ms 67740 KB n=200000
93 Correct 905 ms 66824 KB n=200000
94 Correct 893 ms 66884 KB n=200000
95 Correct 575 ms 67552 KB n=200000
96 Correct 577 ms 67668 KB n=200000
97 Correct 918 ms 66928 KB n=200000
98 Correct 624 ms 67692 KB n=200000
99 Correct 740 ms 67200 KB n=200000
100 Correct 591 ms 67788 KB n=200000
101 Correct 874 ms 66716 KB n=200000
102 Correct 380 ms 68608 KB n=200000
103 Correct 366 ms 68556 KB n=200000
104 Correct 370 ms 68624 KB n=200000
105 Correct 372 ms 68376 KB n=200000
106 Correct 370 ms 68456 KB n=200000
107 Correct 368 ms 68300 KB n=200000
108 Correct 677 ms 67340 KB n=200000
109 Correct 679 ms 67220 KB n=200000
110 Correct 676 ms 67380 KB n=200000
111 Correct 626 ms 67804 KB n=200000
112 Correct 877 ms 66888 KB n=200000
113 Correct 911 ms 66852 KB n=200000
114 Correct 637 ms 67652 KB n=200000
115 Correct 935 ms 66888 KB n=200000
116 Correct 554 ms 67288 KB n=200000
117 Correct 866 ms 66672 KB n=200000
118 Correct 899 ms 66552 KB n=200000
119 Correct 555 ms 67480 KB n=200000
120 Correct 829 ms 66480 KB n=200000
121 Correct 835 ms 66436 KB n=200000
122 Correct 827 ms 66756 KB n=200000
123 Correct 373 ms 67996 KB n=200000
124 Correct 187 ms 49124 KB n=25264