#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 200000;
const int MXLOG = 18;
int par[MAXN+5][MXLOG+1];
vector <int> graf[MAXN+5];
int in[MAXN+5];
int out[MAXN+5];
int tjm;
void dfs(int v, int p){
par[v][0] = p;
in[v] = ++tjm;
for(int j=1; j<=MXLOG; j++) par[v][j] = par[par[v][j-1]][j-1];
for(auto c : graf[v]) if(c != p) dfs(c, v);
out[v] = tjm;
}
int val[MAXN+5];
bool is_parent(int a, int b){
return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}
int lca(int a, int b){
if(is_parent(a, b)) return a;
for(int j=MXLOG; j>=0; j--){
if(!is_parent(par[a][j], b)) a = par[a][j];
}
return par[a][0];
}
set <int> p1[MAXN+5];
set <int> p2[MAXN+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m, q;
cin >> n >> m >> q;
for(int i=1; i<n; i++){
int a, b;
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
dfs(1, 0);
for(int i=1; i<=m; i++){
cin >> val[i];
p1[val[i]].insert(i);
}
for(int i=2; i<=m; i++){
p2[lca(val[i-1], val[i])].insert(i);
}
while(q--){
int tp;
cin >> tp;
if(tp == 1){
int pos, v;
cin >> pos >> v;
p1[val[pos]].erase(pos);
if(pos > 1) p2[lca(val[pos], val[pos-1])].erase(pos);
if(pos < m) p2[lca(val[pos], val[pos+1])].erase(pos+1);
val[pos] = v;
p1[val[pos]].insert(pos);
if(pos > 1) p2[lca(val[pos], val[pos-1])].insert(pos);
if(pos < m) p2[lca(val[pos], val[pos+1])].insert(pos+1);
}
else{
int l, r, v;
cin >> l >> r >> v;
auto x = p1[v].lower_bound(l);
if(x != p1[v].end() && *x <= r){
cout << *x << " " << *x << "\n";
continue;
}
x = p2[v].lower_bound(l+1);
if(x != p2[v].end() && *x <= r){
cout << (*x)-1 << " " << *x << "\n";
continue;
}
cout << "-1 -1\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23816 KB |
n=5 |
2 |
Correct |
14 ms |
23852 KB |
n=100 |
3 |
Correct |
14 ms |
23828 KB |
n=100 |
4 |
Correct |
14 ms |
23780 KB |
n=100 |
5 |
Correct |
15 ms |
23760 KB |
n=100 |
6 |
Correct |
14 ms |
23756 KB |
n=100 |
7 |
Correct |
14 ms |
23816 KB |
n=100 |
8 |
Correct |
14 ms |
23756 KB |
n=100 |
9 |
Correct |
14 ms |
23756 KB |
n=100 |
10 |
Correct |
15 ms |
23728 KB |
n=100 |
11 |
Correct |
14 ms |
23740 KB |
n=100 |
12 |
Correct |
14 ms |
23760 KB |
n=100 |
13 |
Correct |
15 ms |
23800 KB |
n=100 |
14 |
Correct |
15 ms |
23756 KB |
n=100 |
15 |
Correct |
14 ms |
23772 KB |
n=100 |
16 |
Correct |
15 ms |
23756 KB |
n=100 |
17 |
Correct |
16 ms |
23756 KB |
n=100 |
18 |
Correct |
15 ms |
23812 KB |
n=100 |
19 |
Correct |
14 ms |
23816 KB |
n=100 |
20 |
Correct |
14 ms |
23788 KB |
n=100 |
21 |
Correct |
14 ms |
23756 KB |
n=100 |
22 |
Correct |
15 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23812 KB |
n=100 |
24 |
Correct |
15 ms |
23848 KB |
n=100 |
25 |
Correct |
15 ms |
23820 KB |
n=100 |
26 |
Correct |
15 ms |
23756 KB |
n=12 |
27 |
Correct |
14 ms |
23752 KB |
n=100 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23816 KB |
n=5 |
2 |
Correct |
14 ms |
23852 KB |
n=100 |
3 |
Correct |
14 ms |
23828 KB |
n=100 |
4 |
Correct |
14 ms |
23780 KB |
n=100 |
5 |
Correct |
15 ms |
23760 KB |
n=100 |
6 |
Correct |
14 ms |
23756 KB |
n=100 |
7 |
Correct |
14 ms |
23816 KB |
n=100 |
8 |
Correct |
14 ms |
23756 KB |
n=100 |
9 |
Correct |
14 ms |
23756 KB |
n=100 |
10 |
Correct |
15 ms |
23728 KB |
n=100 |
11 |
Correct |
14 ms |
23740 KB |
n=100 |
12 |
Correct |
14 ms |
23760 KB |
n=100 |
13 |
Correct |
15 ms |
23800 KB |
n=100 |
14 |
Correct |
15 ms |
23756 KB |
n=100 |
15 |
Correct |
14 ms |
23772 KB |
n=100 |
16 |
Correct |
15 ms |
23756 KB |
n=100 |
17 |
Correct |
16 ms |
23756 KB |
n=100 |
18 |
Correct |
15 ms |
23812 KB |
n=100 |
19 |
Correct |
14 ms |
23816 KB |
n=100 |
20 |
Correct |
14 ms |
23788 KB |
n=100 |
21 |
Correct |
14 ms |
23756 KB |
n=100 |
22 |
Correct |
15 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23812 KB |
n=100 |
24 |
Correct |
15 ms |
23848 KB |
n=100 |
25 |
Correct |
15 ms |
23820 KB |
n=100 |
26 |
Correct |
15 ms |
23756 KB |
n=12 |
27 |
Correct |
14 ms |
23752 KB |
n=100 |
28 |
Correct |
15 ms |
24012 KB |
n=500 |
29 |
Correct |
14 ms |
23952 KB |
n=500 |
30 |
Correct |
15 ms |
23956 KB |
n=500 |
31 |
Correct |
15 ms |
23920 KB |
n=500 |
32 |
Correct |
15 ms |
23884 KB |
n=500 |
33 |
Correct |
17 ms |
23956 KB |
n=500 |
34 |
Correct |
15 ms |
23912 KB |
n=500 |
35 |
Correct |
16 ms |
23912 KB |
n=500 |
36 |
Correct |
14 ms |
23952 KB |
n=500 |
37 |
Correct |
13 ms |
23884 KB |
n=500 |
38 |
Correct |
14 ms |
23884 KB |
n=500 |
39 |
Correct |
14 ms |
23884 KB |
n=500 |
40 |
Correct |
14 ms |
23936 KB |
n=500 |
41 |
Correct |
13 ms |
23936 KB |
n=500 |
42 |
Correct |
16 ms |
23952 KB |
n=500 |
43 |
Correct |
18 ms |
23844 KB |
n=500 |
44 |
Correct |
14 ms |
23908 KB |
n=500 |
45 |
Correct |
13 ms |
23856 KB |
n=500 |
46 |
Correct |
14 ms |
23956 KB |
n=500 |
47 |
Correct |
18 ms |
23856 KB |
n=500 |
48 |
Correct |
14 ms |
23884 KB |
n=500 |
49 |
Correct |
13 ms |
23864 KB |
n=500 |
50 |
Correct |
14 ms |
23884 KB |
n=500 |
51 |
Correct |
13 ms |
23864 KB |
n=500 |
52 |
Correct |
14 ms |
23956 KB |
n=500 |
53 |
Correct |
14 ms |
23884 KB |
n=500 |
54 |
Correct |
13 ms |
23884 KB |
n=500 |
55 |
Correct |
13 ms |
23824 KB |
n=278 |
56 |
Correct |
17 ms |
23924 KB |
n=500 |
57 |
Correct |
14 ms |
23924 KB |
n=500 |
58 |
Correct |
14 ms |
23884 KB |
n=500 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23816 KB |
n=5 |
2 |
Correct |
14 ms |
23852 KB |
n=100 |
3 |
Correct |
14 ms |
23828 KB |
n=100 |
4 |
Correct |
14 ms |
23780 KB |
n=100 |
5 |
Correct |
15 ms |
23760 KB |
n=100 |
6 |
Correct |
14 ms |
23756 KB |
n=100 |
7 |
Correct |
14 ms |
23816 KB |
n=100 |
8 |
Correct |
14 ms |
23756 KB |
n=100 |
9 |
Correct |
14 ms |
23756 KB |
n=100 |
10 |
Correct |
15 ms |
23728 KB |
n=100 |
11 |
Correct |
14 ms |
23740 KB |
n=100 |
12 |
Correct |
14 ms |
23760 KB |
n=100 |
13 |
Correct |
15 ms |
23800 KB |
n=100 |
14 |
Correct |
15 ms |
23756 KB |
n=100 |
15 |
Correct |
14 ms |
23772 KB |
n=100 |
16 |
Correct |
15 ms |
23756 KB |
n=100 |
17 |
Correct |
16 ms |
23756 KB |
n=100 |
18 |
Correct |
15 ms |
23812 KB |
n=100 |
19 |
Correct |
14 ms |
23816 KB |
n=100 |
20 |
Correct |
14 ms |
23788 KB |
n=100 |
21 |
Correct |
14 ms |
23756 KB |
n=100 |
22 |
Correct |
15 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23812 KB |
n=100 |
24 |
Correct |
15 ms |
23848 KB |
n=100 |
25 |
Correct |
15 ms |
23820 KB |
n=100 |
26 |
Correct |
15 ms |
23756 KB |
n=12 |
27 |
Correct |
14 ms |
23752 KB |
n=100 |
28 |
Correct |
15 ms |
24012 KB |
n=500 |
29 |
Correct |
14 ms |
23952 KB |
n=500 |
30 |
Correct |
15 ms |
23956 KB |
n=500 |
31 |
Correct |
15 ms |
23920 KB |
n=500 |
32 |
Correct |
15 ms |
23884 KB |
n=500 |
33 |
Correct |
17 ms |
23956 KB |
n=500 |
34 |
Correct |
15 ms |
23912 KB |
n=500 |
35 |
Correct |
16 ms |
23912 KB |
n=500 |
36 |
Correct |
14 ms |
23952 KB |
n=500 |
37 |
Correct |
13 ms |
23884 KB |
n=500 |
38 |
Correct |
14 ms |
23884 KB |
n=500 |
39 |
Correct |
14 ms |
23884 KB |
n=500 |
40 |
Correct |
14 ms |
23936 KB |
n=500 |
41 |
Correct |
13 ms |
23936 KB |
n=500 |
42 |
Correct |
16 ms |
23952 KB |
n=500 |
43 |
Correct |
18 ms |
23844 KB |
n=500 |
44 |
Correct |
14 ms |
23908 KB |
n=500 |
45 |
Correct |
13 ms |
23856 KB |
n=500 |
46 |
Correct |
14 ms |
23956 KB |
n=500 |
47 |
Correct |
18 ms |
23856 KB |
n=500 |
48 |
Correct |
14 ms |
23884 KB |
n=500 |
49 |
Correct |
13 ms |
23864 KB |
n=500 |
50 |
Correct |
14 ms |
23884 KB |
n=500 |
51 |
Correct |
13 ms |
23864 KB |
n=500 |
52 |
Correct |
14 ms |
23956 KB |
n=500 |
53 |
Correct |
14 ms |
23884 KB |
n=500 |
54 |
Correct |
13 ms |
23884 KB |
n=500 |
55 |
Correct |
13 ms |
23824 KB |
n=278 |
56 |
Correct |
17 ms |
23924 KB |
n=500 |
57 |
Correct |
14 ms |
23924 KB |
n=500 |
58 |
Correct |
14 ms |
23884 KB |
n=500 |
59 |
Correct |
19 ms |
24252 KB |
n=2000 |
60 |
Correct |
19 ms |
24392 KB |
n=2000 |
61 |
Correct |
18 ms |
24308 KB |
n=2000 |
62 |
Correct |
17 ms |
24252 KB |
n=2000 |
63 |
Correct |
17 ms |
24208 KB |
n=2000 |
64 |
Correct |
18 ms |
24268 KB |
n=2000 |
65 |
Correct |
20 ms |
24316 KB |
n=2000 |
66 |
Correct |
19 ms |
24368 KB |
n=2000 |
67 |
Correct |
20 ms |
24208 KB |
n=2000 |
68 |
Correct |
18 ms |
24256 KB |
n=2000 |
69 |
Correct |
18 ms |
24288 KB |
n=2000 |
70 |
Correct |
16 ms |
24272 KB |
n=2000 |
71 |
Correct |
18 ms |
24224 KB |
n=2000 |
72 |
Correct |
15 ms |
24208 KB |
n=2000 |
73 |
Correct |
15 ms |
24212 KB |
n=2000 |
74 |
Correct |
18 ms |
24268 KB |
n=1844 |
75 |
Correct |
17 ms |
24260 KB |
n=2000 |
76 |
Correct |
17 ms |
24212 KB |
n=2000 |
77 |
Correct |
17 ms |
24220 KB |
n=2000 |
78 |
Correct |
18 ms |
24272 KB |
n=2000 |
79 |
Correct |
17 ms |
24212 KB |
n=2000 |
80 |
Correct |
17 ms |
24340 KB |
n=2000 |
81 |
Correct |
17 ms |
24340 KB |
n=2000 |
82 |
Correct |
16 ms |
24216 KB |
n=2000 |
83 |
Correct |
20 ms |
24324 KB |
n=2000 |
84 |
Correct |
19 ms |
24292 KB |
n=2000 |
85 |
Correct |
17 ms |
24268 KB |
n=2000 |
86 |
Correct |
18 ms |
24336 KB |
n=2000 |
87 |
Correct |
18 ms |
24268 KB |
n=2000 |
88 |
Correct |
17 ms |
24396 KB |
n=2000 |
89 |
Correct |
17 ms |
24396 KB |
n=2000 |
90 |
Correct |
16 ms |
24364 KB |
n=2000 |
91 |
Correct |
16 ms |
24316 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23816 KB |
n=5 |
2 |
Correct |
14 ms |
23852 KB |
n=100 |
3 |
Correct |
14 ms |
23828 KB |
n=100 |
4 |
Correct |
14 ms |
23780 KB |
n=100 |
5 |
Correct |
15 ms |
23760 KB |
n=100 |
6 |
Correct |
14 ms |
23756 KB |
n=100 |
7 |
Correct |
14 ms |
23816 KB |
n=100 |
8 |
Correct |
14 ms |
23756 KB |
n=100 |
9 |
Correct |
14 ms |
23756 KB |
n=100 |
10 |
Correct |
15 ms |
23728 KB |
n=100 |
11 |
Correct |
14 ms |
23740 KB |
n=100 |
12 |
Correct |
14 ms |
23760 KB |
n=100 |
13 |
Correct |
15 ms |
23800 KB |
n=100 |
14 |
Correct |
15 ms |
23756 KB |
n=100 |
15 |
Correct |
14 ms |
23772 KB |
n=100 |
16 |
Correct |
15 ms |
23756 KB |
n=100 |
17 |
Correct |
16 ms |
23756 KB |
n=100 |
18 |
Correct |
15 ms |
23812 KB |
n=100 |
19 |
Correct |
14 ms |
23816 KB |
n=100 |
20 |
Correct |
14 ms |
23788 KB |
n=100 |
21 |
Correct |
14 ms |
23756 KB |
n=100 |
22 |
Correct |
15 ms |
23756 KB |
n=100 |
23 |
Correct |
15 ms |
23812 KB |
n=100 |
24 |
Correct |
15 ms |
23848 KB |
n=100 |
25 |
Correct |
15 ms |
23820 KB |
n=100 |
26 |
Correct |
15 ms |
23756 KB |
n=12 |
27 |
Correct |
14 ms |
23752 KB |
n=100 |
28 |
Correct |
15 ms |
24012 KB |
n=500 |
29 |
Correct |
14 ms |
23952 KB |
n=500 |
30 |
Correct |
15 ms |
23956 KB |
n=500 |
31 |
Correct |
15 ms |
23920 KB |
n=500 |
32 |
Correct |
15 ms |
23884 KB |
n=500 |
33 |
Correct |
17 ms |
23956 KB |
n=500 |
34 |
Correct |
15 ms |
23912 KB |
n=500 |
35 |
Correct |
16 ms |
23912 KB |
n=500 |
36 |
Correct |
14 ms |
23952 KB |
n=500 |
37 |
Correct |
13 ms |
23884 KB |
n=500 |
38 |
Correct |
14 ms |
23884 KB |
n=500 |
39 |
Correct |
14 ms |
23884 KB |
n=500 |
40 |
Correct |
14 ms |
23936 KB |
n=500 |
41 |
Correct |
13 ms |
23936 KB |
n=500 |
42 |
Correct |
16 ms |
23952 KB |
n=500 |
43 |
Correct |
18 ms |
23844 KB |
n=500 |
44 |
Correct |
14 ms |
23908 KB |
n=500 |
45 |
Correct |
13 ms |
23856 KB |
n=500 |
46 |
Correct |
14 ms |
23956 KB |
n=500 |
47 |
Correct |
18 ms |
23856 KB |
n=500 |
48 |
Correct |
14 ms |
23884 KB |
n=500 |
49 |
Correct |
13 ms |
23864 KB |
n=500 |
50 |
Correct |
14 ms |
23884 KB |
n=500 |
51 |
Correct |
13 ms |
23864 KB |
n=500 |
52 |
Correct |
14 ms |
23956 KB |
n=500 |
53 |
Correct |
14 ms |
23884 KB |
n=500 |
54 |
Correct |
13 ms |
23884 KB |
n=500 |
55 |
Correct |
13 ms |
23824 KB |
n=278 |
56 |
Correct |
17 ms |
23924 KB |
n=500 |
57 |
Correct |
14 ms |
23924 KB |
n=500 |
58 |
Correct |
14 ms |
23884 KB |
n=500 |
59 |
Correct |
19 ms |
24252 KB |
n=2000 |
60 |
Correct |
19 ms |
24392 KB |
n=2000 |
61 |
Correct |
18 ms |
24308 KB |
n=2000 |
62 |
Correct |
17 ms |
24252 KB |
n=2000 |
63 |
Correct |
17 ms |
24208 KB |
n=2000 |
64 |
Correct |
18 ms |
24268 KB |
n=2000 |
65 |
Correct |
20 ms |
24316 KB |
n=2000 |
66 |
Correct |
19 ms |
24368 KB |
n=2000 |
67 |
Correct |
20 ms |
24208 KB |
n=2000 |
68 |
Correct |
18 ms |
24256 KB |
n=2000 |
69 |
Correct |
18 ms |
24288 KB |
n=2000 |
70 |
Correct |
16 ms |
24272 KB |
n=2000 |
71 |
Correct |
18 ms |
24224 KB |
n=2000 |
72 |
Correct |
15 ms |
24208 KB |
n=2000 |
73 |
Correct |
15 ms |
24212 KB |
n=2000 |
74 |
Correct |
18 ms |
24268 KB |
n=1844 |
75 |
Correct |
17 ms |
24260 KB |
n=2000 |
76 |
Correct |
17 ms |
24212 KB |
n=2000 |
77 |
Correct |
17 ms |
24220 KB |
n=2000 |
78 |
Correct |
18 ms |
24272 KB |
n=2000 |
79 |
Correct |
17 ms |
24212 KB |
n=2000 |
80 |
Correct |
17 ms |
24340 KB |
n=2000 |
81 |
Correct |
17 ms |
24340 KB |
n=2000 |
82 |
Correct |
16 ms |
24216 KB |
n=2000 |
83 |
Correct |
20 ms |
24324 KB |
n=2000 |
84 |
Correct |
19 ms |
24292 KB |
n=2000 |
85 |
Correct |
17 ms |
24268 KB |
n=2000 |
86 |
Correct |
18 ms |
24336 KB |
n=2000 |
87 |
Correct |
18 ms |
24268 KB |
n=2000 |
88 |
Correct |
17 ms |
24396 KB |
n=2000 |
89 |
Correct |
17 ms |
24396 KB |
n=2000 |
90 |
Correct |
16 ms |
24364 KB |
n=2000 |
91 |
Correct |
16 ms |
24316 KB |
n=2000 |
92 |
Correct |
813 ms |
74552 KB |
n=200000 |
93 |
Correct |
1217 ms |
79392 KB |
n=200000 |
94 |
Correct |
1108 ms |
82776 KB |
n=200000 |
95 |
Correct |
802 ms |
74220 KB |
n=200000 |
96 |
Correct |
760 ms |
74304 KB |
n=200000 |
97 |
Correct |
1258 ms |
78520 KB |
n=200000 |
98 |
Correct |
828 ms |
74292 KB |
n=200000 |
99 |
Correct |
915 ms |
74548 KB |
n=200000 |
100 |
Correct |
792 ms |
74336 KB |
n=200000 |
101 |
Correct |
1025 ms |
84020 KB |
n=200000 |
102 |
Correct |
486 ms |
75528 KB |
n=200000 |
103 |
Correct |
498 ms |
75476 KB |
n=200000 |
104 |
Correct |
548 ms |
75556 KB |
n=200000 |
105 |
Correct |
501 ms |
75924 KB |
n=200000 |
106 |
Correct |
535 ms |
75952 KB |
n=200000 |
107 |
Correct |
498 ms |
75948 KB |
n=200000 |
108 |
Correct |
839 ms |
74396 KB |
n=200000 |
109 |
Correct |
812 ms |
74388 KB |
n=200000 |
110 |
Correct |
824 ms |
74584 KB |
n=200000 |
111 |
Correct |
736 ms |
73764 KB |
n=200000 |
112 |
Correct |
995 ms |
82932 KB |
n=200000 |
113 |
Correct |
1099 ms |
78384 KB |
n=200000 |
114 |
Correct |
790 ms |
73788 KB |
n=200000 |
115 |
Correct |
1301 ms |
76404 KB |
n=200000 |
116 |
Correct |
800 ms |
74532 KB |
n=200000 |
117 |
Correct |
1250 ms |
83380 KB |
n=200000 |
118 |
Correct |
1348 ms |
77248 KB |
n=200000 |
119 |
Correct |
765 ms |
74456 KB |
n=200000 |
120 |
Correct |
1080 ms |
83000 KB |
n=200000 |
121 |
Correct |
1004 ms |
82924 KB |
n=200000 |
122 |
Correct |
1029 ms |
83200 KB |
n=200000 |
123 |
Correct |
503 ms |
75660 KB |
n=200000 |
124 |
Correct |
233 ms |
38592 KB |
n=25264 |