#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int lg = 18;
const int mx = 200'000;
vvi anc(1+mx, vi(1+lg, 1));
vi edge[1+mx];
vi depth(1+mx, 0);
void dfs(int u)
{
for(int v: edge[u])
{
if(anc[u][0] == v) continue;
depth[v] = 1 + depth[u];
anc[v][0] = u;
dfs(v);
}
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
for(int e = 0; e <= lg; e++)
if((depth[v] - depth[u]) & (1 << e))
v = anc[v][e];
if(u == v) return u;
for(int e = lg; e >= 0; e--)
{
if(anc[u][e] != anc[v][e])
{
u = anc[u][e];
v = anc[v][e];
}
}
return anc[u][0];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
for(int e = 1; e <= n-1; e++)
{
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1);
for(int e = 1; e <= lg; e++)
for(int u = 1; u <= n; u++)
anc[u][e] = anc[ anc[u][e-1] ][e-1];
vi a(1+m);
for(int i = 1; i <= m; i++) cin >> a[i];
vi L(m);
for(int i = 1; i < m; i++) L[i] = lca(a[i], a[i+1]);
// for(int i = 1; i < m; i++) cerr << i << " : " << L[i] << '\n';
set<int> occ[1+n];
for(int i = 1; i < m; i++)
occ[L[i]].insert(i);
set<int> occ_i[1+n];
for(int i = 1; i <= m; i++) occ_i[a[i]].insert(i);
// for(int v = 1; v <= n; v++)
// {
// cerr << v << " : ";
// for(int o: occ_i[v]) cerr << o << ' ';
// cerr << '\n';
// }
for(int x = 1; x <= q; x++)
{
int t;
cin >> t;
if(t == 1)
{
int p, v;
cin >> p >> v;
if(p > 1)
occ[L[p-1]].erase(p-1);
if(p < m)
occ[L[p]].erase(p);
occ_i[a[p]].erase(p);
a[p] = v;
if(p > 1)
L[p-1] = lca(a[p-1], a[p]);
if(p < m)
L[p] = lca(a[p], a[p+1]);
if(p > 1)
occ[L[p-1]].insert(p-1);
if(p < m)
occ[L[p]].insert(p);
occ_i[a[p]].insert(p);
// for(int i = 1; i <= m; i++) cerr << a[i] << ' ';
// cerr << '\n';
// for(int i = 1; i < m; i++) cerr << i << " : " << L[i] << '\n';
}
else
{
int l, r, v;
cin >> l >> r >> v;
auto z = occ[v].lower_bound(l);
if(z == occ[v].end() || *z >= r)
{
// cerr << "#\n";
// cerr << "oiv = ";
// for(int o: occ_i[v]) cerr << o << ' ';
// cerr << '\n';
auto z2 = occ_i[v].lower_bound(l);
if(z2 == occ_i[v].end() || *z2 > r) cout << "-1 -1\n";
else cout << *z2 << ' ' << *z2 << '\n';
}
else cout << *z << ' ' << (*z)+1 << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
29260 KB |
n=5 |
2 |
Correct |
19 ms |
29260 KB |
n=100 |
3 |
Correct |
19 ms |
29280 KB |
n=100 |
4 |
Correct |
24 ms |
29264 KB |
n=100 |
5 |
Correct |
19 ms |
29260 KB |
n=100 |
6 |
Correct |
19 ms |
29260 KB |
n=100 |
7 |
Correct |
19 ms |
29260 KB |
n=100 |
8 |
Correct |
19 ms |
29252 KB |
n=100 |
9 |
Correct |
19 ms |
29232 KB |
n=100 |
10 |
Correct |
19 ms |
29260 KB |
n=100 |
11 |
Correct |
19 ms |
29288 KB |
n=100 |
12 |
Correct |
19 ms |
29296 KB |
n=100 |
13 |
Correct |
19 ms |
29260 KB |
n=100 |
14 |
Correct |
18 ms |
29256 KB |
n=100 |
15 |
Correct |
19 ms |
29260 KB |
n=100 |
16 |
Correct |
21 ms |
29392 KB |
n=100 |
17 |
Correct |
20 ms |
29292 KB |
n=100 |
18 |
Correct |
19 ms |
29208 KB |
n=100 |
19 |
Correct |
19 ms |
29192 KB |
n=100 |
20 |
Correct |
19 ms |
29300 KB |
n=100 |
21 |
Correct |
21 ms |
29292 KB |
n=100 |
22 |
Correct |
19 ms |
29284 KB |
n=100 |
23 |
Correct |
27 ms |
29216 KB |
n=100 |
24 |
Correct |
19 ms |
29292 KB |
n=100 |
25 |
Correct |
24 ms |
29388 KB |
n=100 |
26 |
Correct |
18 ms |
29200 KB |
n=12 |
27 |
Correct |
19 ms |
29216 KB |
n=100 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
29260 KB |
n=5 |
2 |
Correct |
19 ms |
29260 KB |
n=100 |
3 |
Correct |
19 ms |
29280 KB |
n=100 |
4 |
Correct |
24 ms |
29264 KB |
n=100 |
5 |
Correct |
19 ms |
29260 KB |
n=100 |
6 |
Correct |
19 ms |
29260 KB |
n=100 |
7 |
Correct |
19 ms |
29260 KB |
n=100 |
8 |
Correct |
19 ms |
29252 KB |
n=100 |
9 |
Correct |
19 ms |
29232 KB |
n=100 |
10 |
Correct |
19 ms |
29260 KB |
n=100 |
11 |
Correct |
19 ms |
29288 KB |
n=100 |
12 |
Correct |
19 ms |
29296 KB |
n=100 |
13 |
Correct |
19 ms |
29260 KB |
n=100 |
14 |
Correct |
18 ms |
29256 KB |
n=100 |
15 |
Correct |
19 ms |
29260 KB |
n=100 |
16 |
Correct |
21 ms |
29392 KB |
n=100 |
17 |
Correct |
20 ms |
29292 KB |
n=100 |
18 |
Correct |
19 ms |
29208 KB |
n=100 |
19 |
Correct |
19 ms |
29192 KB |
n=100 |
20 |
Correct |
19 ms |
29300 KB |
n=100 |
21 |
Correct |
21 ms |
29292 KB |
n=100 |
22 |
Correct |
19 ms |
29284 KB |
n=100 |
23 |
Correct |
27 ms |
29216 KB |
n=100 |
24 |
Correct |
19 ms |
29292 KB |
n=100 |
25 |
Correct |
24 ms |
29388 KB |
n=100 |
26 |
Correct |
18 ms |
29200 KB |
n=12 |
27 |
Correct |
19 ms |
29216 KB |
n=100 |
28 |
Correct |
19 ms |
29416 KB |
n=500 |
29 |
Correct |
19 ms |
29420 KB |
n=500 |
30 |
Correct |
21 ms |
29388 KB |
n=500 |
31 |
Correct |
20 ms |
29380 KB |
n=500 |
32 |
Correct |
20 ms |
29280 KB |
n=500 |
33 |
Correct |
19 ms |
29364 KB |
n=500 |
34 |
Correct |
20 ms |
29388 KB |
n=500 |
35 |
Correct |
21 ms |
29300 KB |
n=500 |
36 |
Correct |
20 ms |
29320 KB |
n=500 |
37 |
Correct |
20 ms |
29380 KB |
n=500 |
38 |
Correct |
20 ms |
29296 KB |
n=500 |
39 |
Correct |
20 ms |
29372 KB |
n=500 |
40 |
Correct |
19 ms |
29388 KB |
n=500 |
41 |
Correct |
20 ms |
29388 KB |
n=500 |
42 |
Correct |
19 ms |
29316 KB |
n=500 |
43 |
Correct |
20 ms |
29324 KB |
n=500 |
44 |
Correct |
21 ms |
29308 KB |
n=500 |
45 |
Correct |
19 ms |
29380 KB |
n=500 |
46 |
Correct |
20 ms |
29388 KB |
n=500 |
47 |
Correct |
19 ms |
29300 KB |
n=500 |
48 |
Correct |
20 ms |
29356 KB |
n=500 |
49 |
Correct |
19 ms |
29300 KB |
n=500 |
50 |
Correct |
19 ms |
29388 KB |
n=500 |
51 |
Correct |
20 ms |
29304 KB |
n=500 |
52 |
Correct |
20 ms |
29388 KB |
n=500 |
53 |
Correct |
23 ms |
29292 KB |
n=500 |
54 |
Correct |
19 ms |
29392 KB |
n=500 |
55 |
Correct |
19 ms |
29300 KB |
n=278 |
56 |
Correct |
20 ms |
29388 KB |
n=500 |
57 |
Correct |
20 ms |
29404 KB |
n=500 |
58 |
Correct |
19 ms |
29336 KB |
n=500 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
29260 KB |
n=5 |
2 |
Correct |
19 ms |
29260 KB |
n=100 |
3 |
Correct |
19 ms |
29280 KB |
n=100 |
4 |
Correct |
24 ms |
29264 KB |
n=100 |
5 |
Correct |
19 ms |
29260 KB |
n=100 |
6 |
Correct |
19 ms |
29260 KB |
n=100 |
7 |
Correct |
19 ms |
29260 KB |
n=100 |
8 |
Correct |
19 ms |
29252 KB |
n=100 |
9 |
Correct |
19 ms |
29232 KB |
n=100 |
10 |
Correct |
19 ms |
29260 KB |
n=100 |
11 |
Correct |
19 ms |
29288 KB |
n=100 |
12 |
Correct |
19 ms |
29296 KB |
n=100 |
13 |
Correct |
19 ms |
29260 KB |
n=100 |
14 |
Correct |
18 ms |
29256 KB |
n=100 |
15 |
Correct |
19 ms |
29260 KB |
n=100 |
16 |
Correct |
21 ms |
29392 KB |
n=100 |
17 |
Correct |
20 ms |
29292 KB |
n=100 |
18 |
Correct |
19 ms |
29208 KB |
n=100 |
19 |
Correct |
19 ms |
29192 KB |
n=100 |
20 |
Correct |
19 ms |
29300 KB |
n=100 |
21 |
Correct |
21 ms |
29292 KB |
n=100 |
22 |
Correct |
19 ms |
29284 KB |
n=100 |
23 |
Correct |
27 ms |
29216 KB |
n=100 |
24 |
Correct |
19 ms |
29292 KB |
n=100 |
25 |
Correct |
24 ms |
29388 KB |
n=100 |
26 |
Correct |
18 ms |
29200 KB |
n=12 |
27 |
Correct |
19 ms |
29216 KB |
n=100 |
28 |
Correct |
19 ms |
29416 KB |
n=500 |
29 |
Correct |
19 ms |
29420 KB |
n=500 |
30 |
Correct |
21 ms |
29388 KB |
n=500 |
31 |
Correct |
20 ms |
29380 KB |
n=500 |
32 |
Correct |
20 ms |
29280 KB |
n=500 |
33 |
Correct |
19 ms |
29364 KB |
n=500 |
34 |
Correct |
20 ms |
29388 KB |
n=500 |
35 |
Correct |
21 ms |
29300 KB |
n=500 |
36 |
Correct |
20 ms |
29320 KB |
n=500 |
37 |
Correct |
20 ms |
29380 KB |
n=500 |
38 |
Correct |
20 ms |
29296 KB |
n=500 |
39 |
Correct |
20 ms |
29372 KB |
n=500 |
40 |
Correct |
19 ms |
29388 KB |
n=500 |
41 |
Correct |
20 ms |
29388 KB |
n=500 |
42 |
Correct |
19 ms |
29316 KB |
n=500 |
43 |
Correct |
20 ms |
29324 KB |
n=500 |
44 |
Correct |
21 ms |
29308 KB |
n=500 |
45 |
Correct |
19 ms |
29380 KB |
n=500 |
46 |
Correct |
20 ms |
29388 KB |
n=500 |
47 |
Correct |
19 ms |
29300 KB |
n=500 |
48 |
Correct |
20 ms |
29356 KB |
n=500 |
49 |
Correct |
19 ms |
29300 KB |
n=500 |
50 |
Correct |
19 ms |
29388 KB |
n=500 |
51 |
Correct |
20 ms |
29304 KB |
n=500 |
52 |
Correct |
20 ms |
29388 KB |
n=500 |
53 |
Correct |
23 ms |
29292 KB |
n=500 |
54 |
Correct |
19 ms |
29392 KB |
n=500 |
55 |
Correct |
19 ms |
29300 KB |
n=278 |
56 |
Correct |
20 ms |
29388 KB |
n=500 |
57 |
Correct |
20 ms |
29404 KB |
n=500 |
58 |
Correct |
19 ms |
29336 KB |
n=500 |
59 |
Correct |
22 ms |
29716 KB |
n=2000 |
60 |
Correct |
23 ms |
29728 KB |
n=2000 |
61 |
Correct |
23 ms |
29772 KB |
n=2000 |
62 |
Correct |
22 ms |
29708 KB |
n=2000 |
63 |
Correct |
22 ms |
29676 KB |
n=2000 |
64 |
Correct |
23 ms |
29740 KB |
n=2000 |
65 |
Correct |
21 ms |
29668 KB |
n=2000 |
66 |
Correct |
22 ms |
29736 KB |
n=2000 |
67 |
Correct |
22 ms |
29728 KB |
n=2000 |
68 |
Correct |
22 ms |
29704 KB |
n=2000 |
69 |
Correct |
21 ms |
29780 KB |
n=2000 |
70 |
Correct |
24 ms |
29828 KB |
n=2000 |
71 |
Correct |
28 ms |
29764 KB |
n=2000 |
72 |
Correct |
23 ms |
29808 KB |
n=2000 |
73 |
Correct |
21 ms |
29736 KB |
n=2000 |
74 |
Correct |
23 ms |
29696 KB |
n=1844 |
75 |
Correct |
23 ms |
29756 KB |
n=2000 |
76 |
Correct |
22 ms |
29712 KB |
n=2000 |
77 |
Correct |
22 ms |
29684 KB |
n=2000 |
78 |
Correct |
22 ms |
29764 KB |
n=2000 |
79 |
Correct |
22 ms |
29728 KB |
n=2000 |
80 |
Correct |
25 ms |
29848 KB |
n=2000 |
81 |
Correct |
23 ms |
29780 KB |
n=2000 |
82 |
Correct |
25 ms |
29800 KB |
n=2000 |
83 |
Correct |
22 ms |
29732 KB |
n=2000 |
84 |
Correct |
23 ms |
29692 KB |
n=2000 |
85 |
Correct |
23 ms |
29772 KB |
n=2000 |
86 |
Correct |
24 ms |
29688 KB |
n=2000 |
87 |
Correct |
28 ms |
29772 KB |
n=2000 |
88 |
Correct |
21 ms |
29708 KB |
n=2000 |
89 |
Correct |
21 ms |
29772 KB |
n=2000 |
90 |
Correct |
24 ms |
29764 KB |
n=2000 |
91 |
Correct |
22 ms |
29692 KB |
n=2000 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
29260 KB |
n=5 |
2 |
Correct |
19 ms |
29260 KB |
n=100 |
3 |
Correct |
19 ms |
29280 KB |
n=100 |
4 |
Correct |
24 ms |
29264 KB |
n=100 |
5 |
Correct |
19 ms |
29260 KB |
n=100 |
6 |
Correct |
19 ms |
29260 KB |
n=100 |
7 |
Correct |
19 ms |
29260 KB |
n=100 |
8 |
Correct |
19 ms |
29252 KB |
n=100 |
9 |
Correct |
19 ms |
29232 KB |
n=100 |
10 |
Correct |
19 ms |
29260 KB |
n=100 |
11 |
Correct |
19 ms |
29288 KB |
n=100 |
12 |
Correct |
19 ms |
29296 KB |
n=100 |
13 |
Correct |
19 ms |
29260 KB |
n=100 |
14 |
Correct |
18 ms |
29256 KB |
n=100 |
15 |
Correct |
19 ms |
29260 KB |
n=100 |
16 |
Correct |
21 ms |
29392 KB |
n=100 |
17 |
Correct |
20 ms |
29292 KB |
n=100 |
18 |
Correct |
19 ms |
29208 KB |
n=100 |
19 |
Correct |
19 ms |
29192 KB |
n=100 |
20 |
Correct |
19 ms |
29300 KB |
n=100 |
21 |
Correct |
21 ms |
29292 KB |
n=100 |
22 |
Correct |
19 ms |
29284 KB |
n=100 |
23 |
Correct |
27 ms |
29216 KB |
n=100 |
24 |
Correct |
19 ms |
29292 KB |
n=100 |
25 |
Correct |
24 ms |
29388 KB |
n=100 |
26 |
Correct |
18 ms |
29200 KB |
n=12 |
27 |
Correct |
19 ms |
29216 KB |
n=100 |
28 |
Correct |
19 ms |
29416 KB |
n=500 |
29 |
Correct |
19 ms |
29420 KB |
n=500 |
30 |
Correct |
21 ms |
29388 KB |
n=500 |
31 |
Correct |
20 ms |
29380 KB |
n=500 |
32 |
Correct |
20 ms |
29280 KB |
n=500 |
33 |
Correct |
19 ms |
29364 KB |
n=500 |
34 |
Correct |
20 ms |
29388 KB |
n=500 |
35 |
Correct |
21 ms |
29300 KB |
n=500 |
36 |
Correct |
20 ms |
29320 KB |
n=500 |
37 |
Correct |
20 ms |
29380 KB |
n=500 |
38 |
Correct |
20 ms |
29296 KB |
n=500 |
39 |
Correct |
20 ms |
29372 KB |
n=500 |
40 |
Correct |
19 ms |
29388 KB |
n=500 |
41 |
Correct |
20 ms |
29388 KB |
n=500 |
42 |
Correct |
19 ms |
29316 KB |
n=500 |
43 |
Correct |
20 ms |
29324 KB |
n=500 |
44 |
Correct |
21 ms |
29308 KB |
n=500 |
45 |
Correct |
19 ms |
29380 KB |
n=500 |
46 |
Correct |
20 ms |
29388 KB |
n=500 |
47 |
Correct |
19 ms |
29300 KB |
n=500 |
48 |
Correct |
20 ms |
29356 KB |
n=500 |
49 |
Correct |
19 ms |
29300 KB |
n=500 |
50 |
Correct |
19 ms |
29388 KB |
n=500 |
51 |
Correct |
20 ms |
29304 KB |
n=500 |
52 |
Correct |
20 ms |
29388 KB |
n=500 |
53 |
Correct |
23 ms |
29292 KB |
n=500 |
54 |
Correct |
19 ms |
29392 KB |
n=500 |
55 |
Correct |
19 ms |
29300 KB |
n=278 |
56 |
Correct |
20 ms |
29388 KB |
n=500 |
57 |
Correct |
20 ms |
29404 KB |
n=500 |
58 |
Correct |
19 ms |
29336 KB |
n=500 |
59 |
Correct |
22 ms |
29716 KB |
n=2000 |
60 |
Correct |
23 ms |
29728 KB |
n=2000 |
61 |
Correct |
23 ms |
29772 KB |
n=2000 |
62 |
Correct |
22 ms |
29708 KB |
n=2000 |
63 |
Correct |
22 ms |
29676 KB |
n=2000 |
64 |
Correct |
23 ms |
29740 KB |
n=2000 |
65 |
Correct |
21 ms |
29668 KB |
n=2000 |
66 |
Correct |
22 ms |
29736 KB |
n=2000 |
67 |
Correct |
22 ms |
29728 KB |
n=2000 |
68 |
Correct |
22 ms |
29704 KB |
n=2000 |
69 |
Correct |
21 ms |
29780 KB |
n=2000 |
70 |
Correct |
24 ms |
29828 KB |
n=2000 |
71 |
Correct |
28 ms |
29764 KB |
n=2000 |
72 |
Correct |
23 ms |
29808 KB |
n=2000 |
73 |
Correct |
21 ms |
29736 KB |
n=2000 |
74 |
Correct |
23 ms |
29696 KB |
n=1844 |
75 |
Correct |
23 ms |
29756 KB |
n=2000 |
76 |
Correct |
22 ms |
29712 KB |
n=2000 |
77 |
Correct |
22 ms |
29684 KB |
n=2000 |
78 |
Correct |
22 ms |
29764 KB |
n=2000 |
79 |
Correct |
22 ms |
29728 KB |
n=2000 |
80 |
Correct |
25 ms |
29848 KB |
n=2000 |
81 |
Correct |
23 ms |
29780 KB |
n=2000 |
82 |
Correct |
25 ms |
29800 KB |
n=2000 |
83 |
Correct |
22 ms |
29732 KB |
n=2000 |
84 |
Correct |
23 ms |
29692 KB |
n=2000 |
85 |
Correct |
23 ms |
29772 KB |
n=2000 |
86 |
Correct |
24 ms |
29688 KB |
n=2000 |
87 |
Correct |
28 ms |
29772 KB |
n=2000 |
88 |
Correct |
21 ms |
29708 KB |
n=2000 |
89 |
Correct |
21 ms |
29772 KB |
n=2000 |
90 |
Correct |
24 ms |
29764 KB |
n=2000 |
91 |
Correct |
22 ms |
29692 KB |
n=2000 |
92 |
Correct |
700 ms |
83208 KB |
n=200000 |
93 |
Correct |
983 ms |
83216 KB |
n=200000 |
94 |
Correct |
1022 ms |
82852 KB |
n=200000 |
95 |
Correct |
720 ms |
82912 KB |
n=200000 |
96 |
Correct |
682 ms |
83016 KB |
n=200000 |
97 |
Correct |
1006 ms |
82180 KB |
n=200000 |
98 |
Correct |
696 ms |
82556 KB |
n=200000 |
99 |
Correct |
814 ms |
81912 KB |
n=200000 |
100 |
Correct |
703 ms |
82532 KB |
n=200000 |
101 |
Correct |
909 ms |
81724 KB |
n=200000 |
102 |
Correct |
422 ms |
82932 KB |
n=200000 |
103 |
Correct |
469 ms |
82836 KB |
n=200000 |
104 |
Correct |
412 ms |
83008 KB |
n=200000 |
105 |
Correct |
426 ms |
83248 KB |
n=200000 |
106 |
Correct |
422 ms |
83412 KB |
n=200000 |
107 |
Correct |
426 ms |
83180 KB |
n=200000 |
108 |
Correct |
813 ms |
81888 KB |
n=200000 |
109 |
Correct |
825 ms |
81760 KB |
n=200000 |
110 |
Correct |
827 ms |
81764 KB |
n=200000 |
111 |
Correct |
747 ms |
81500 KB |
n=200000 |
112 |
Correct |
877 ms |
82048 KB |
n=200000 |
113 |
Correct |
967 ms |
81952 KB |
n=200000 |
114 |
Correct |
711 ms |
82012 KB |
n=200000 |
115 |
Correct |
992 ms |
83496 KB |
n=200000 |
116 |
Correct |
657 ms |
83020 KB |
n=200000 |
117 |
Correct |
876 ms |
83088 KB |
n=200000 |
118 |
Correct |
1036 ms |
83008 KB |
n=200000 |
119 |
Correct |
769 ms |
82692 KB |
n=200000 |
120 |
Correct |
956 ms |
80892 KB |
n=200000 |
121 |
Correct |
913 ms |
80952 KB |
n=200000 |
122 |
Correct |
831 ms |
82676 KB |
n=200000 |
123 |
Correct |
440 ms |
84400 KB |
n=200000 |
124 |
Correct |
204 ms |
43820 KB |
n=25264 |