//https://oj.uz/problem/view/IZhO18_treearray
#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;
vector <int> adj[N];
set <int> ans[2][N];
int n, m, q, a[N], p[N][20], d[N];
void dfs(int u){
for (int i = 0; i < (int)adj[u].size(); i++){
int v = adj[u][i];
if (v == p[u][0]) continue;
d[v] = d[u] + 1; p[v][0] = u;
dfs(v);
}
}
int lca(int u, int v){
if (d[u] < d[v]) swap(u, v);
for (int i = 19; i >= 0; i--) if (d[u] - (1 << i) >= d[v]) u = p[u][i];
for (int i = 19; i >= 0; i--) if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
return ((u != v) ? p[u][0] : u);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for (int i = 2; i <= n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
dfs(1);
for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++) p[j][i] = p[p[j][i-1]][i-1];
for (int i = 1; i <= m; i++) cin >> a[i];
for (int i = 1; i <= m; i++) ans[0][a[i]].insert(i);
for (int i = 1; i < m; i++) ans[1][lca(a[i], a[i+1])].insert(i);
while (q--){
int type;
cin >> type;
if (type == 1){
int pos, v;
cin >> pos >> v;
ans[0][a[pos]].erase(pos);
if (pos > 1) ans[1][lca(a[pos-1], a[pos])].erase(pos-1);
if (pos < n) ans[1][lca(a[pos], a[pos+1])].erase(pos);
a[pos] = v;
ans[0][a[pos]].insert(pos);
if (pos > 1) ans[1][lca(a[pos-1], a[pos])].insert(pos-1);
if (pos < n) ans[1][lca(a[pos], a[pos+1])].insert(pos);
}
else{
int l, r, v;
cin >> l >> r >> v;
set <int> ::iterator it = ans[0][v].lower_bound(l);
if (it != ans[0][v].end() && *it <= r) {
cout << *it << " " << *it << "\n";
continue;
}
it = ans[1][v].lower_bound(l);
if (it != ans[1][v].end() && *it < r){
cout << *it << " " << (*it)+1 << "\n";
continue;
}
cout << "-1 -1\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
n=5 |
2 |
Correct |
21 ms |
23908 KB |
n=100 |
3 |
Correct |
20 ms |
24076 KB |
n=100 |
4 |
Correct |
20 ms |
24136 KB |
n=100 |
5 |
Correct |
24 ms |
24136 KB |
n=100 |
6 |
Correct |
19 ms |
24176 KB |
n=100 |
7 |
Correct |
23 ms |
24228 KB |
n=100 |
8 |
Correct |
20 ms |
24228 KB |
n=100 |
9 |
Correct |
20 ms |
24228 KB |
n=100 |
10 |
Correct |
20 ms |
24228 KB |
n=100 |
11 |
Correct |
21 ms |
24228 KB |
n=100 |
12 |
Correct |
20 ms |
24296 KB |
n=100 |
13 |
Correct |
19 ms |
24296 KB |
n=100 |
14 |
Correct |
21 ms |
24296 KB |
n=100 |
15 |
Correct |
19 ms |
24296 KB |
n=100 |
16 |
Correct |
22 ms |
24296 KB |
n=100 |
17 |
Correct |
20 ms |
24296 KB |
n=100 |
18 |
Correct |
19 ms |
24296 KB |
n=100 |
19 |
Correct |
21 ms |
24296 KB |
n=100 |
20 |
Correct |
22 ms |
24296 KB |
n=100 |
21 |
Correct |
23 ms |
24332 KB |
n=100 |
22 |
Correct |
22 ms |
24332 KB |
n=100 |
23 |
Correct |
21 ms |
24332 KB |
n=100 |
24 |
Correct |
22 ms |
24332 KB |
n=100 |
25 |
Correct |
19 ms |
24332 KB |
n=100 |
26 |
Correct |
20 ms |
24332 KB |
n=12 |
27 |
Correct |
22 ms |
24332 KB |
n=100 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
n=5 |
2 |
Correct |
21 ms |
23908 KB |
n=100 |
3 |
Correct |
20 ms |
24076 KB |
n=100 |
4 |
Correct |
20 ms |
24136 KB |
n=100 |
5 |
Correct |
24 ms |
24136 KB |
n=100 |
6 |
Correct |
19 ms |
24176 KB |
n=100 |
7 |
Correct |
23 ms |
24228 KB |
n=100 |
8 |
Correct |
20 ms |
24228 KB |
n=100 |
9 |
Correct |
20 ms |
24228 KB |
n=100 |
10 |
Correct |
20 ms |
24228 KB |
n=100 |
11 |
Correct |
21 ms |
24228 KB |
n=100 |
12 |
Correct |
20 ms |
24296 KB |
n=100 |
13 |
Correct |
19 ms |
24296 KB |
n=100 |
14 |
Correct |
21 ms |
24296 KB |
n=100 |
15 |
Correct |
19 ms |
24296 KB |
n=100 |
16 |
Correct |
22 ms |
24296 KB |
n=100 |
17 |
Correct |
20 ms |
24296 KB |
n=100 |
18 |
Correct |
19 ms |
24296 KB |
n=100 |
19 |
Correct |
21 ms |
24296 KB |
n=100 |
20 |
Correct |
22 ms |
24296 KB |
n=100 |
21 |
Correct |
23 ms |
24332 KB |
n=100 |
22 |
Correct |
22 ms |
24332 KB |
n=100 |
23 |
Correct |
21 ms |
24332 KB |
n=100 |
24 |
Correct |
22 ms |
24332 KB |
n=100 |
25 |
Correct |
19 ms |
24332 KB |
n=100 |
26 |
Correct |
20 ms |
24332 KB |
n=12 |
27 |
Correct |
22 ms |
24332 KB |
n=100 |
28 |
Correct |
21 ms |
24360 KB |
n=500 |
29 |
Correct |
20 ms |
24372 KB |
n=500 |
30 |
Correct |
21 ms |
24392 KB |
n=500 |
31 |
Correct |
21 ms |
24404 KB |
n=500 |
32 |
Correct |
23 ms |
24420 KB |
n=500 |
33 |
Correct |
21 ms |
24432 KB |
n=500 |
34 |
Correct |
20 ms |
24448 KB |
n=500 |
35 |
Correct |
20 ms |
24464 KB |
n=500 |
36 |
Correct |
20 ms |
24480 KB |
n=500 |
37 |
Correct |
20 ms |
24560 KB |
n=500 |
38 |
Correct |
21 ms |
24560 KB |
n=500 |
39 |
Correct |
21 ms |
24560 KB |
n=500 |
40 |
Correct |
20 ms |
24560 KB |
n=500 |
41 |
Correct |
22 ms |
24560 KB |
n=500 |
42 |
Correct |
21 ms |
24560 KB |
n=500 |
43 |
Correct |
20 ms |
24572 KB |
n=500 |
44 |
Correct |
21 ms |
24584 KB |
n=500 |
45 |
Correct |
20 ms |
24596 KB |
n=500 |
46 |
Correct |
21 ms |
24608 KB |
n=500 |
47 |
Correct |
21 ms |
24624 KB |
n=500 |
48 |
Correct |
26 ms |
24644 KB |
n=500 |
49 |
Correct |
21 ms |
24656 KB |
n=500 |
50 |
Correct |
22 ms |
24800 KB |
n=500 |
51 |
Correct |
21 ms |
24800 KB |
n=500 |
52 |
Correct |
21 ms |
24800 KB |
n=500 |
53 |
Correct |
20 ms |
24800 KB |
n=500 |
54 |
Correct |
20 ms |
24800 KB |
n=500 |
55 |
Correct |
19 ms |
24800 KB |
n=278 |
56 |
Correct |
20 ms |
24800 KB |
n=500 |
57 |
Correct |
21 ms |
24800 KB |
n=500 |
58 |
Correct |
21 ms |
24800 KB |
n=500 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
n=5 |
2 |
Correct |
21 ms |
23908 KB |
n=100 |
3 |
Correct |
20 ms |
24076 KB |
n=100 |
4 |
Correct |
20 ms |
24136 KB |
n=100 |
5 |
Correct |
24 ms |
24136 KB |
n=100 |
6 |
Correct |
19 ms |
24176 KB |
n=100 |
7 |
Correct |
23 ms |
24228 KB |
n=100 |
8 |
Correct |
20 ms |
24228 KB |
n=100 |
9 |
Correct |
20 ms |
24228 KB |
n=100 |
10 |
Correct |
20 ms |
24228 KB |
n=100 |
11 |
Correct |
21 ms |
24228 KB |
n=100 |
12 |
Correct |
20 ms |
24296 KB |
n=100 |
13 |
Correct |
19 ms |
24296 KB |
n=100 |
14 |
Correct |
21 ms |
24296 KB |
n=100 |
15 |
Correct |
19 ms |
24296 KB |
n=100 |
16 |
Correct |
22 ms |
24296 KB |
n=100 |
17 |
Correct |
20 ms |
24296 KB |
n=100 |
18 |
Correct |
19 ms |
24296 KB |
n=100 |
19 |
Correct |
21 ms |
24296 KB |
n=100 |
20 |
Correct |
22 ms |
24296 KB |
n=100 |
21 |
Correct |
23 ms |
24332 KB |
n=100 |
22 |
Correct |
22 ms |
24332 KB |
n=100 |
23 |
Correct |
21 ms |
24332 KB |
n=100 |
24 |
Correct |
22 ms |
24332 KB |
n=100 |
25 |
Correct |
19 ms |
24332 KB |
n=100 |
26 |
Correct |
20 ms |
24332 KB |
n=12 |
27 |
Correct |
22 ms |
24332 KB |
n=100 |
28 |
Correct |
21 ms |
24360 KB |
n=500 |
29 |
Correct |
20 ms |
24372 KB |
n=500 |
30 |
Correct |
21 ms |
24392 KB |
n=500 |
31 |
Correct |
21 ms |
24404 KB |
n=500 |
32 |
Correct |
23 ms |
24420 KB |
n=500 |
33 |
Correct |
21 ms |
24432 KB |
n=500 |
34 |
Correct |
20 ms |
24448 KB |
n=500 |
35 |
Correct |
20 ms |
24464 KB |
n=500 |
36 |
Correct |
20 ms |
24480 KB |
n=500 |
37 |
Correct |
20 ms |
24560 KB |
n=500 |
38 |
Correct |
21 ms |
24560 KB |
n=500 |
39 |
Correct |
21 ms |
24560 KB |
n=500 |
40 |
Correct |
20 ms |
24560 KB |
n=500 |
41 |
Correct |
22 ms |
24560 KB |
n=500 |
42 |
Correct |
21 ms |
24560 KB |
n=500 |
43 |
Correct |
20 ms |
24572 KB |
n=500 |
44 |
Correct |
21 ms |
24584 KB |
n=500 |
45 |
Correct |
20 ms |
24596 KB |
n=500 |
46 |
Correct |
21 ms |
24608 KB |
n=500 |
47 |
Correct |
21 ms |
24624 KB |
n=500 |
48 |
Correct |
26 ms |
24644 KB |
n=500 |
49 |
Correct |
21 ms |
24656 KB |
n=500 |
50 |
Correct |
22 ms |
24800 KB |
n=500 |
51 |
Correct |
21 ms |
24800 KB |
n=500 |
52 |
Correct |
21 ms |
24800 KB |
n=500 |
53 |
Correct |
20 ms |
24800 KB |
n=500 |
54 |
Correct |
20 ms |
24800 KB |
n=500 |
55 |
Correct |
19 ms |
24800 KB |
n=278 |
56 |
Correct |
20 ms |
24800 KB |
n=500 |
57 |
Correct |
21 ms |
24800 KB |
n=500 |
58 |
Correct |
21 ms |
24800 KB |
n=500 |
59 |
Correct |
24 ms |
25176 KB |
n=2000 |
60 |
Correct |
24 ms |
25356 KB |
n=2000 |
61 |
Correct |
24 ms |
25432 KB |
n=2000 |
62 |
Correct |
24 ms |
25432 KB |
n=2000 |
63 |
Correct |
24 ms |
25444 KB |
n=2000 |
64 |
Correct |
24 ms |
25624 KB |
n=2000 |
65 |
Correct |
24 ms |
25676 KB |
n=2000 |
66 |
Correct |
24 ms |
25732 KB |
n=2000 |
67 |
Correct |
24 ms |
25788 KB |
n=2000 |
68 |
Correct |
25 ms |
25828 KB |
n=2000 |
69 |
Correct |
23 ms |
25828 KB |
n=2000 |
70 |
Correct |
23 ms |
25828 KB |
n=2000 |
71 |
Correct |
23 ms |
25868 KB |
n=2000 |
72 |
Correct |
23 ms |
26048 KB |
n=2000 |
73 |
Correct |
22 ms |
26048 KB |
n=2000 |
74 |
Correct |
24 ms |
26048 KB |
n=1844 |
75 |
Correct |
28 ms |
26080 KB |
n=2000 |
76 |
Correct |
24 ms |
26148 KB |
n=2000 |
77 |
Correct |
24 ms |
26200 KB |
n=2000 |
78 |
Correct |
26 ms |
26232 KB |
n=2000 |
79 |
Correct |
31 ms |
26232 KB |
n=2000 |
80 |
Correct |
24 ms |
26360 KB |
n=2000 |
81 |
Correct |
24 ms |
26360 KB |
n=2000 |
82 |
Correct |
24 ms |
26360 KB |
n=2000 |
83 |
Correct |
28 ms |
26360 KB |
n=2000 |
84 |
Correct |
25 ms |
26360 KB |
n=2000 |
85 |
Correct |
26 ms |
26364 KB |
n=2000 |
86 |
Correct |
24 ms |
26364 KB |
n=2000 |
87 |
Correct |
24 ms |
26364 KB |
n=2000 |
88 |
Correct |
26 ms |
26364 KB |
n=2000 |
89 |
Correct |
24 ms |
26364 KB |
n=2000 |
90 |
Correct |
27 ms |
26364 KB |
n=2000 |
91 |
Correct |
26 ms |
26364 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
n=5 |
2 |
Correct |
21 ms |
23908 KB |
n=100 |
3 |
Correct |
20 ms |
24076 KB |
n=100 |
4 |
Correct |
20 ms |
24136 KB |
n=100 |
5 |
Correct |
24 ms |
24136 KB |
n=100 |
6 |
Correct |
19 ms |
24176 KB |
n=100 |
7 |
Correct |
23 ms |
24228 KB |
n=100 |
8 |
Correct |
20 ms |
24228 KB |
n=100 |
9 |
Correct |
20 ms |
24228 KB |
n=100 |
10 |
Correct |
20 ms |
24228 KB |
n=100 |
11 |
Correct |
21 ms |
24228 KB |
n=100 |
12 |
Correct |
20 ms |
24296 KB |
n=100 |
13 |
Correct |
19 ms |
24296 KB |
n=100 |
14 |
Correct |
21 ms |
24296 KB |
n=100 |
15 |
Correct |
19 ms |
24296 KB |
n=100 |
16 |
Correct |
22 ms |
24296 KB |
n=100 |
17 |
Correct |
20 ms |
24296 KB |
n=100 |
18 |
Correct |
19 ms |
24296 KB |
n=100 |
19 |
Correct |
21 ms |
24296 KB |
n=100 |
20 |
Correct |
22 ms |
24296 KB |
n=100 |
21 |
Correct |
23 ms |
24332 KB |
n=100 |
22 |
Correct |
22 ms |
24332 KB |
n=100 |
23 |
Correct |
21 ms |
24332 KB |
n=100 |
24 |
Correct |
22 ms |
24332 KB |
n=100 |
25 |
Correct |
19 ms |
24332 KB |
n=100 |
26 |
Correct |
20 ms |
24332 KB |
n=12 |
27 |
Correct |
22 ms |
24332 KB |
n=100 |
28 |
Correct |
21 ms |
24360 KB |
n=500 |
29 |
Correct |
20 ms |
24372 KB |
n=500 |
30 |
Correct |
21 ms |
24392 KB |
n=500 |
31 |
Correct |
21 ms |
24404 KB |
n=500 |
32 |
Correct |
23 ms |
24420 KB |
n=500 |
33 |
Correct |
21 ms |
24432 KB |
n=500 |
34 |
Correct |
20 ms |
24448 KB |
n=500 |
35 |
Correct |
20 ms |
24464 KB |
n=500 |
36 |
Correct |
20 ms |
24480 KB |
n=500 |
37 |
Correct |
20 ms |
24560 KB |
n=500 |
38 |
Correct |
21 ms |
24560 KB |
n=500 |
39 |
Correct |
21 ms |
24560 KB |
n=500 |
40 |
Correct |
20 ms |
24560 KB |
n=500 |
41 |
Correct |
22 ms |
24560 KB |
n=500 |
42 |
Correct |
21 ms |
24560 KB |
n=500 |
43 |
Correct |
20 ms |
24572 KB |
n=500 |
44 |
Correct |
21 ms |
24584 KB |
n=500 |
45 |
Correct |
20 ms |
24596 KB |
n=500 |
46 |
Correct |
21 ms |
24608 KB |
n=500 |
47 |
Correct |
21 ms |
24624 KB |
n=500 |
48 |
Correct |
26 ms |
24644 KB |
n=500 |
49 |
Correct |
21 ms |
24656 KB |
n=500 |
50 |
Correct |
22 ms |
24800 KB |
n=500 |
51 |
Correct |
21 ms |
24800 KB |
n=500 |
52 |
Correct |
21 ms |
24800 KB |
n=500 |
53 |
Correct |
20 ms |
24800 KB |
n=500 |
54 |
Correct |
20 ms |
24800 KB |
n=500 |
55 |
Correct |
19 ms |
24800 KB |
n=278 |
56 |
Correct |
20 ms |
24800 KB |
n=500 |
57 |
Correct |
21 ms |
24800 KB |
n=500 |
58 |
Correct |
21 ms |
24800 KB |
n=500 |
59 |
Correct |
24 ms |
25176 KB |
n=2000 |
60 |
Correct |
24 ms |
25356 KB |
n=2000 |
61 |
Correct |
24 ms |
25432 KB |
n=2000 |
62 |
Correct |
24 ms |
25432 KB |
n=2000 |
63 |
Correct |
24 ms |
25444 KB |
n=2000 |
64 |
Correct |
24 ms |
25624 KB |
n=2000 |
65 |
Correct |
24 ms |
25676 KB |
n=2000 |
66 |
Correct |
24 ms |
25732 KB |
n=2000 |
67 |
Correct |
24 ms |
25788 KB |
n=2000 |
68 |
Correct |
25 ms |
25828 KB |
n=2000 |
69 |
Correct |
23 ms |
25828 KB |
n=2000 |
70 |
Correct |
23 ms |
25828 KB |
n=2000 |
71 |
Correct |
23 ms |
25868 KB |
n=2000 |
72 |
Correct |
23 ms |
26048 KB |
n=2000 |
73 |
Correct |
22 ms |
26048 KB |
n=2000 |
74 |
Correct |
24 ms |
26048 KB |
n=1844 |
75 |
Correct |
28 ms |
26080 KB |
n=2000 |
76 |
Correct |
24 ms |
26148 KB |
n=2000 |
77 |
Correct |
24 ms |
26200 KB |
n=2000 |
78 |
Correct |
26 ms |
26232 KB |
n=2000 |
79 |
Correct |
31 ms |
26232 KB |
n=2000 |
80 |
Correct |
24 ms |
26360 KB |
n=2000 |
81 |
Correct |
24 ms |
26360 KB |
n=2000 |
82 |
Correct |
24 ms |
26360 KB |
n=2000 |
83 |
Correct |
28 ms |
26360 KB |
n=2000 |
84 |
Correct |
25 ms |
26360 KB |
n=2000 |
85 |
Correct |
26 ms |
26364 KB |
n=2000 |
86 |
Correct |
24 ms |
26364 KB |
n=2000 |
87 |
Correct |
24 ms |
26364 KB |
n=2000 |
88 |
Correct |
26 ms |
26364 KB |
n=2000 |
89 |
Correct |
24 ms |
26364 KB |
n=2000 |
90 |
Correct |
27 ms |
26364 KB |
n=2000 |
91 |
Correct |
26 ms |
26364 KB |
n=2000 |
92 |
Correct |
972 ms |
70004 KB |
n=200000 |
93 |
Correct |
1431 ms |
84440 KB |
n=200000 |
94 |
Correct |
1403 ms |
97796 KB |
n=200000 |
95 |
Correct |
1006 ms |
97796 KB |
n=200000 |
96 |
Correct |
927 ms |
98328 KB |
n=200000 |
97 |
Correct |
1434 ms |
111432 KB |
n=200000 |
98 |
Correct |
944 ms |
112516 KB |
n=200000 |
99 |
Correct |
1171 ms |
119080 KB |
n=200000 |
100 |
Correct |
1012 ms |
126128 KB |
n=200000 |
101 |
Correct |
1424 ms |
148356 KB |
n=200000 |
102 |
Correct |
537 ms |
148356 KB |
n=200000 |
103 |
Correct |
540 ms |
148356 KB |
n=200000 |
104 |
Correct |
534 ms |
154696 KB |
n=200000 |
105 |
Correct |
533 ms |
161788 KB |
n=200000 |
106 |
Correct |
559 ms |
169140 KB |
n=200000 |
107 |
Correct |
540 ms |
176504 KB |
n=200000 |
108 |
Correct |
1151 ms |
182476 KB |
n=200000 |
109 |
Correct |
1159 ms |
189344 KB |
n=200000 |
110 |
Correct |
1118 ms |
196212 KB |
n=200000 |
111 |
Correct |
1022 ms |
202544 KB |
n=200000 |
112 |
Correct |
1436 ms |
223208 KB |
n=200000 |
113 |
Correct |
1511 ms |
223312 KB |
n=200000 |
114 |
Correct |
941 ms |
224020 KB |
n=200000 |
115 |
Correct |
1352 ms |
233464 KB |
n=200000 |
116 |
Correct |
925 ms |
238428 KB |
n=200000 |
117 |
Correct |
1368 ms |
259896 KB |
n=200000 |
118 |
Correct |
1401 ms |
259896 KB |
n=200000 |
119 |
Correct |
938 ms |
260576 KB |
n=200000 |
120 |
Correct |
1459 ms |
262144 KB |
n=200000 |
121 |
Correct |
1347 ms |
262144 KB |
n=200000 |
122 |
Correct |
1339 ms |
262144 KB |
n=200000 |
123 |
Correct |
527 ms |
262144 KB |
n=200000 |
124 |
Incorrect |
294 ms |
262144 KB |
Wrong range. |