oj.uz

Submission #492387

# Submission time Handle Problem Language Result Execution time Memory
492387 2021-12-07T04:03:06 Z vuhoanggiap Birthday gift (IZhO18_treearray) C++17
100 / 100
 830 ms 102348 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxN = 2e5 + 1; 
int n, m, q; 
vector<int> adj[maxN]; 

int f[maxN], s[2 * maxN], euler;  
int h[maxN]; 

void dfs(int u, int p = 1) {
	s[++euler] = u; 
	f[u] = euler; 
	for (auto v : adj[u]) {
		if (v == p)
			continue; 
		h[v] = h[u] + 1; 
		dfs(v, u); 
		s[++euler] = u; 
	}
}

int lg[2 * maxN]; 
int sp[2 * maxN][20]; 

void build() {
	lg[1] = 0; 
	for (int i = 2; i <= euler; i++) 
		lg[i] = lg[i >> 1] + 1; 
	for (int len = 0; (1 << len) <= euler; len++) {
		for (int i = 1; i + (1 << len) - 1 <= euler; i++) {
			if (!len) 
				sp[i][0] = s[i]; 
			else {
				if (h[sp[i][len - 1]] < h[sp[i + (1 << (len - 1))][len - 1]])
					sp[i][len] = sp[i][len - 1]; 
				else 
					sp[i][len] = sp[i + (1 << (len - 1))][len - 1]; 
			}
		}
	}
}

int lca(int u, int v) {
	int l = f[u], r = f[v]; 
	if (l > r) 
		swap(l, r); 
	int Lg = lg[r - l + 1]; 
	if (h[sp[l][Lg]] < h[sp[r - (1 << Lg) + 1][Lg]])
		return sp[l][Lg]; 
	return sp[r - (1 << Lg) + 1][Lg]; 
}

int a[maxN]; 
set<int> id[maxN], id2[maxN]; 

void add(int i) { 
	if (!i || i == n) 
		return; 
	int val = lca(a[i], a[i + 1]); 
	id2[val].insert(i); 
}

void rem(int i) {
	if (!i || i == n) 
		return; 
	int val = lca(a[i], a[i + 1]); 
	id2[val].erase(i);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> m >> q; 
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; 
		adj[u].pb(v); adj[v].pb(u); 
	}
//5 4 4
//1 2
//3 1
//3 4
//5 3
//4 5 2 3
//2 1 3 1
//1 3 5
//2 3 4 5
//2 1 3 1
	dfs(1); 
	build();
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		id[a[i]].insert(i); 
		add(i - 1); 
	}
//	cout << "id: "; for (int i = 1; i <= n; i++) {
//		cout << "val: " << i << '\t'; 
//		for (auto x : id[i]) cout << x << ' '; cout << '\n'; 
//	}
//	cout << "id2: "; 
//	for (int i = 1; i <= n; i++) {
//		cout << "val: " << i << '\t'; 
//		for (auto x : id2[i]) cout << x << ' '; cout << '\n'; 
//	}
	for (int i = 1; i <= q; i++) {
		int type; cin >> type; 
		if (type == 1) {
			int pos, v; cin >> pos >> v; 
			id[a[pos]].erase(pos); 
			rem(pos - 1); 
			rem(pos); 
			a[pos] = v; 
			add(pos); 
			add(pos - 1); 
			id[a[pos]].insert(pos); 
		}
		else {
			int l, r, v; cin >> l >> r >> v; 
			set<int>::iterator it = id[v].lower_bound(l); 
			bool foundAns = false; 
			if (it != id[v].end()) {
				int val = *it; 
				if (val <= r) {
					cout << val << ' ' << val << '\n';
					foundAns = true;  
				}
			}
			it = id2[v].lower_bound(l); 
			if (it != id2[v].end() && !foundAns) {
				int val = *it; 
				if (val < r) {
					cout << val << ' ' << val + 1 << '\n'; 
					foundAns = true; 
				}
			}
			if (!foundAns) 
				cout << -1 << ' ' << -1 << '\n'; 
		}
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB n=5
2 Correct 12 ms 23756 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 11 ms 23820 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23756 KB n=100
7 Correct 11 ms 23800 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 12 ms 23756 KB n=100
10 Correct 12 ms 23860 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 12 ms 23860 KB n=100
13 Correct 12 ms 23840 KB n=100
14 Correct 12 ms 23780 KB n=100
15 Correct 12 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23856 KB n=100
18 Correct 12 ms 23812 KB n=100
19 Correct 12 ms 23832 KB n=100
20 Correct 12 ms 23756 KB n=100
21 Correct 12 ms 23740 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23860 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23884 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 11 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB n=5
2 Correct 12 ms 23756 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 11 ms 23820 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23756 KB n=100
7 Correct 11 ms 23800 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 12 ms 23756 KB n=100
10 Correct 12 ms 23860 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 12 ms 23860 KB n=100
13 Correct 12 ms 23840 KB n=100
14 Correct 12 ms 23780 KB n=100
15 Correct 12 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23856 KB n=100
18 Correct 12 ms 23812 KB n=100
19 Correct 12 ms 23832 KB n=100
20 Correct 12 ms 23756 KB n=100
21 Correct 12 ms 23740 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23860 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23884 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 11 ms 23756 KB n=100
28 Correct 14 ms 23936 KB n=500
29 Correct 13 ms 24012 KB n=500
30 Correct 14 ms 23884 KB n=500
31 Correct 14 ms 23992 KB n=500
32 Correct 13 ms 23884 KB n=500
33 Correct 13 ms 23884 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 15 ms 24024 KB n=500
36 Correct 13 ms 23960 KB n=500
37 Correct 15 ms 23884 KB n=500
38 Correct 13 ms 23992 KB n=500
39 Correct 14 ms 23884 KB n=500
40 Correct 13 ms 23884 KB n=500
41 Correct 13 ms 23884 KB n=500
42 Correct 14 ms 23884 KB n=500
43 Correct 13 ms 23976 KB n=500
44 Correct 14 ms 23884 KB n=500
45 Correct 14 ms 23952 KB n=500
46 Correct 14 ms 24012 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 13 ms 23940 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 23884 KB n=500
51 Correct 13 ms 23884 KB n=500
52 Correct 13 ms 23992 KB n=500
53 Correct 16 ms 24000 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23884 KB n=278
56 Correct 15 ms 24020 KB n=500
57 Correct 13 ms 24020 KB n=500
58 Correct 13 ms 23884 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB n=5
2 Correct 12 ms 23756 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 11 ms 23820 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23756 KB n=100
7 Correct 11 ms 23800 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 12 ms 23756 KB n=100
10 Correct 12 ms 23860 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 12 ms 23860 KB n=100
13 Correct 12 ms 23840 KB n=100
14 Correct 12 ms 23780 KB n=100
15 Correct 12 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23856 KB n=100
18 Correct 12 ms 23812 KB n=100
19 Correct 12 ms 23832 KB n=100
20 Correct 12 ms 23756 KB n=100
21 Correct 12 ms 23740 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23860 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23884 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 11 ms 23756 KB n=100
28 Correct 14 ms 23936 KB n=500
29 Correct 13 ms 24012 KB n=500
30 Correct 14 ms 23884 KB n=500
31 Correct 14 ms 23992 KB n=500
32 Correct 13 ms 23884 KB n=500
33 Correct 13 ms 23884 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 15 ms 24024 KB n=500
36 Correct 13 ms 23960 KB n=500
37 Correct 15 ms 23884 KB n=500
38 Correct 13 ms 23992 KB n=500
39 Correct 14 ms 23884 KB n=500
40 Correct 13 ms 23884 KB n=500
41 Correct 13 ms 23884 KB n=500
42 Correct 14 ms 23884 KB n=500
43 Correct 13 ms 23976 KB n=500
44 Correct 14 ms 23884 KB n=500
45 Correct 14 ms 23952 KB n=500
46 Correct 14 ms 24012 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 13 ms 23940 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 23884 KB n=500
51 Correct 13 ms 23884 KB n=500
52 Correct 13 ms 23992 KB n=500
53 Correct 16 ms 24000 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23884 KB n=278
56 Correct 15 ms 24020 KB n=500
57 Correct 13 ms 24020 KB n=500
58 Correct 13 ms 23884 KB n=500
59 Correct 14 ms 24436 KB n=2000
60 Correct 15 ms 24584 KB n=2000
61 Correct 15 ms 24524 KB n=2000
62 Correct 17 ms 24400 KB n=2000
63 Correct 15 ms 24372 KB n=2000
64 Correct 15 ms 24484 KB n=2000
65 Correct 14 ms 24396 KB n=2000
66 Correct 15 ms 24524 KB n=2000
67 Correct 15 ms 24396 KB n=2000
68 Correct 17 ms 24524 KB n=2000
69 Correct 14 ms 24396 KB n=2000
70 Correct 15 ms 24424 KB n=2000
71 Correct 15 ms 24396 KB n=2000
72 Correct 14 ms 24396 KB n=2000
73 Correct 16 ms 24444 KB n=2000
74 Correct 15 ms 24436 KB n=1844
75 Correct 15 ms 24440 KB n=2000
76 Correct 15 ms 24396 KB n=2000
77 Correct 18 ms 24440 KB n=2000
78 Correct 14 ms 24396 KB n=2000
79 Correct 19 ms 24392 KB n=2000
80 Correct 16 ms 24500 KB n=2000
81 Correct 17 ms 24476 KB n=2000
82 Correct 15 ms 24396 KB n=2000
83 Correct 15 ms 24560 KB n=2000
84 Correct 15 ms 24396 KB n=2000
85 Correct 14 ms 24508 KB n=2000
86 Correct 15 ms 24416 KB n=2000
87 Correct 15 ms 24396 KB n=2000
88 Correct 19 ms 24524 KB n=2000
89 Correct 19 ms 24524 KB n=2000
90 Correct 15 ms 24624 KB n=2000
91 Correct 14 ms 24460 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB n=5
2 Correct 12 ms 23756 KB n=100
3 Correct 14 ms 23756 KB n=100
4 Correct 11 ms 23820 KB n=100
5 Correct 12 ms 23756 KB n=100
6 Correct 12 ms 23756 KB n=100
7 Correct 11 ms 23800 KB n=100
8 Correct 11 ms 23756 KB n=100
9 Correct 12 ms 23756 KB n=100
10 Correct 12 ms 23860 KB n=100
11 Correct 12 ms 23756 KB n=100
12 Correct 12 ms 23860 KB n=100
13 Correct 12 ms 23840 KB n=100
14 Correct 12 ms 23780 KB n=100
15 Correct 12 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 12 ms 23856 KB n=100
18 Correct 12 ms 23812 KB n=100
19 Correct 12 ms 23832 KB n=100
20 Correct 12 ms 23756 KB n=100
21 Correct 12 ms 23740 KB n=100
22 Correct 12 ms 23756 KB n=100
23 Correct 12 ms 23860 KB n=100
24 Correct 12 ms 23756 KB n=100
25 Correct 13 ms 23884 KB n=100
26 Correct 13 ms 23756 KB n=12
27 Correct 11 ms 23756 KB n=100
28 Correct 14 ms 23936 KB n=500
29 Correct 13 ms 24012 KB n=500
30 Correct 14 ms 23884 KB n=500
31 Correct 14 ms 23992 KB n=500
32 Correct 13 ms 23884 KB n=500
33 Correct 13 ms 23884 KB n=500
34 Correct 13 ms 23884 KB n=500
35 Correct 15 ms 24024 KB n=500
36 Correct 13 ms 23960 KB n=500
37 Correct 15 ms 23884 KB n=500
38 Correct 13 ms 23992 KB n=500
39 Correct 14 ms 23884 KB n=500
40 Correct 13 ms 23884 KB n=500
41 Correct 13 ms 23884 KB n=500
42 Correct 14 ms 23884 KB n=500
43 Correct 13 ms 23976 KB n=500
44 Correct 14 ms 23884 KB n=500
45 Correct 14 ms 23952 KB n=500
46 Correct 14 ms 24012 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 13 ms 23940 KB n=500
49 Correct 12 ms 24012 KB n=500
50 Correct 13 ms 23884 KB n=500
51 Correct 13 ms 23884 KB n=500
52 Correct 13 ms 23992 KB n=500
53 Correct 16 ms 24000 KB n=500
54 Correct 15 ms 24012 KB n=500
55 Correct 14 ms 23884 KB n=278
56 Correct 15 ms 24020 KB n=500
57 Correct 13 ms 24020 KB n=500
58 Correct 13 ms 23884 KB n=500
59 Correct 14 ms 24436 KB n=2000
60 Correct 15 ms 24584 KB n=2000
61 Correct 15 ms 24524 KB n=2000
62 Correct 17 ms 24400 KB n=2000
63 Correct 15 ms 24372 KB n=2000
64 Correct 15 ms 24484 KB n=2000
65 Correct 14 ms 24396 KB n=2000
66 Correct 15 ms 24524 KB n=2000
67 Correct 15 ms 24396 KB n=2000
68 Correct 17 ms 24524 KB n=2000
69 Correct 14 ms 24396 KB n=2000
70 Correct 15 ms 24424 KB n=2000
71 Correct 15 ms 24396 KB n=2000
72 Correct 14 ms 24396 KB n=2000
73 Correct 16 ms 24444 KB n=2000
74 Correct 15 ms 24436 KB n=1844
75 Correct 15 ms 24440 KB n=2000
76 Correct 15 ms 24396 KB n=2000
77 Correct 18 ms 24440 KB n=2000
78 Correct 14 ms 24396 KB n=2000
79 Correct 19 ms 24392 KB n=2000
80 Correct 16 ms 24500 KB n=2000
81 Correct 17 ms 24476 KB n=2000
82 Correct 15 ms 24396 KB n=2000
83 Correct 15 ms 24560 KB n=2000
84 Correct 15 ms 24396 KB n=2000
85 Correct 14 ms 24508 KB n=2000
86 Correct 15 ms 24416 KB n=2000
87 Correct 15 ms 24396 KB n=2000
88 Correct 19 ms 24524 KB n=2000
89 Correct 19 ms 24524 KB n=2000
90 Correct 15 ms 24624 KB n=2000
91 Correct 14 ms 24460 KB n=2000
92 Correct 817 ms 87572 KB n=200000
93 Correct 748 ms 94304 KB n=200000
94 Correct 679 ms 100024 KB n=200000
95 Correct 698 ms 87596 KB n=200000
96 Correct 776 ms 87608 KB n=200000
97 Correct 760 ms 92908 KB n=200000
98 Correct 751 ms 87668 KB n=200000
99 Correct 794 ms 86888 KB n=200000
100 Correct 724 ms 87760 KB n=200000
101 Correct 696 ms 102072 KB n=200000
102 Correct 425 ms 88384 KB n=200000
103 Correct 433 ms 88428 KB n=200000
104 Correct 414 ms 88484 KB n=200000
105 Correct 410 ms 88128 KB n=200000
106 Correct 413 ms 88132 KB n=200000
107 Correct 414 ms 88192 KB n=200000
108 Correct 722 ms 87408 KB n=200000
109 Correct 732 ms 87176 KB n=200000
110 Correct 730 ms 87068 KB n=200000
111 Correct 742 ms 87412 KB n=200000
112 Correct 669 ms 100384 KB n=200000
113 Correct 751 ms 92752 KB n=200000
114 Correct 743 ms 87400 KB n=200000
115 Correct 830 ms 89388 KB n=200000
116 Correct 669 ms 87220 KB n=200000
117 Correct 692 ms 101104 KB n=200000
118 Correct 801 ms 91080 KB n=200000
119 Correct 674 ms 87196 KB n=200000
120 Correct 596 ms 101900 KB n=200000
121 Correct 628 ms 101908 KB n=200000
122 Correct 675 ms 102348 KB n=200000
123 Correct 461 ms 87880 KB n=200000
124 Correct 171 ms 39956 KB n=25264