#include <bits/stdc++.h>
using namespace std;
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int n, m, q;
vector<int> adj[N];
int h[N], par[N][lg + 1];
int a[N];
set<int> pos[N], f[N];
void dfs(int u, int p) {
par[u][0] = p;
for (int i = 1; i <= lg; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
for (int v : adj[u]) if (v != p) {
h[v] = h[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v) {
if (h[u] < h[v]) swap(u, v);
for (int i = lg; i >= 0; --i) if (h[par[u][i]] >= h[v]) u = par[u][i];
if (u == v) return u;
for (int i = lg; i >= 0; --i) if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
h[0] = -1;
dfs(1, 0);
for (int i = 1; i <= m; ++i) {
cin >> a[i];
pos[a[i]].insert(i);
}
for (int i = 2; i <= m; ++i) {
f[lca(a[i - 1], a[i])].insert(i - 1);
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
int id, v;
cin >> id >> v;
if (id > 1) f[lca(a[id - 1], a[id])].erase(id - 1);
if (id < m) f[lca(a[id], a[id + 1])].erase(id);
pos[a[id]].erase(id);
a[id] = v;
if (id > 1) f[lca(a[id - 1], a[id])].insert(id - 1);
if (id < m) f[lca(a[id], a[id + 1])].insert(id);
pos[a[id]].insert(id);
}
else {
int l, r, v;
cin >> l >> r >> v;
auto it = pos[v].lower_bound(l);
if (it != pos[v].end() && *it <= r) {
cout << *it << ' ' << *it << '\n';
}
else {
it = f[v].lower_bound(l);
if (it != f[v].end() && *it + 1 <= r) {
cout << *it << ' ' << *it + 1 << '\n';
}
else {
cout << -1 << ' ' << -1 << '\n';
}
}
}
}
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
122708 KB |
n=5 |
2 |
Correct |
25 ms |
122704 KB |
n=100 |
3 |
Correct |
24 ms |
122716 KB |
n=100 |
4 |
Correct |
24 ms |
122716 KB |
n=100 |
5 |
Correct |
24 ms |
122716 KB |
n=100 |
6 |
Correct |
25 ms |
122800 KB |
n=100 |
7 |
Correct |
24 ms |
122712 KB |
n=100 |
8 |
Correct |
26 ms |
122716 KB |
n=100 |
9 |
Correct |
25 ms |
122704 KB |
n=100 |
10 |
Correct |
25 ms |
122712 KB |
n=100 |
11 |
Correct |
26 ms |
122964 KB |
n=100 |
12 |
Correct |
25 ms |
122712 KB |
n=100 |
13 |
Correct |
24 ms |
122716 KB |
n=100 |
14 |
Correct |
25 ms |
122716 KB |
n=100 |
15 |
Correct |
24 ms |
122716 KB |
n=100 |
16 |
Correct |
24 ms |
122716 KB |
n=100 |
17 |
Correct |
24 ms |
122704 KB |
n=100 |
18 |
Correct |
25 ms |
122748 KB |
n=100 |
19 |
Correct |
25 ms |
122716 KB |
n=100 |
20 |
Correct |
24 ms |
122716 KB |
n=100 |
21 |
Correct |
26 ms |
122768 KB |
n=100 |
22 |
Correct |
24 ms |
122716 KB |
n=100 |
23 |
Correct |
24 ms |
122580 KB |
n=100 |
24 |
Correct |
27 ms |
122968 KB |
n=100 |
25 |
Correct |
24 ms |
122716 KB |
n=100 |
26 |
Correct |
25 ms |
122716 KB |
n=12 |
27 |
Correct |
24 ms |
122712 KB |
n=100 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
122708 KB |
n=5 |
2 |
Correct |
25 ms |
122704 KB |
n=100 |
3 |
Correct |
24 ms |
122716 KB |
n=100 |
4 |
Correct |
24 ms |
122716 KB |
n=100 |
5 |
Correct |
24 ms |
122716 KB |
n=100 |
6 |
Correct |
25 ms |
122800 KB |
n=100 |
7 |
Correct |
24 ms |
122712 KB |
n=100 |
8 |
Correct |
26 ms |
122716 KB |
n=100 |
9 |
Correct |
25 ms |
122704 KB |
n=100 |
10 |
Correct |
25 ms |
122712 KB |
n=100 |
11 |
Correct |
26 ms |
122964 KB |
n=100 |
12 |
Correct |
25 ms |
122712 KB |
n=100 |
13 |
Correct |
24 ms |
122716 KB |
n=100 |
14 |
Correct |
25 ms |
122716 KB |
n=100 |
15 |
Correct |
24 ms |
122716 KB |
n=100 |
16 |
Correct |
24 ms |
122716 KB |
n=100 |
17 |
Correct |
24 ms |
122704 KB |
n=100 |
18 |
Correct |
25 ms |
122748 KB |
n=100 |
19 |
Correct |
25 ms |
122716 KB |
n=100 |
20 |
Correct |
24 ms |
122716 KB |
n=100 |
21 |
Correct |
26 ms |
122768 KB |
n=100 |
22 |
Correct |
24 ms |
122716 KB |
n=100 |
23 |
Correct |
24 ms |
122580 KB |
n=100 |
24 |
Correct |
27 ms |
122968 KB |
n=100 |
25 |
Correct |
24 ms |
122716 KB |
n=100 |
26 |
Correct |
25 ms |
122716 KB |
n=12 |
27 |
Correct |
24 ms |
122712 KB |
n=100 |
28 |
Correct |
24 ms |
122716 KB |
n=500 |
29 |
Correct |
25 ms |
122728 KB |
n=500 |
30 |
Correct |
25 ms |
122756 KB |
n=500 |
31 |
Correct |
24 ms |
122892 KB |
n=500 |
32 |
Correct |
25 ms |
122716 KB |
n=500 |
33 |
Correct |
28 ms |
122844 KB |
n=500 |
34 |
Correct |
25 ms |
122712 KB |
n=500 |
35 |
Correct |
25 ms |
122716 KB |
n=500 |
36 |
Correct |
24 ms |
122792 KB |
n=500 |
37 |
Correct |
25 ms |
122712 KB |
n=500 |
38 |
Correct |
26 ms |
122744 KB |
n=500 |
39 |
Correct |
26 ms |
122708 KB |
n=500 |
40 |
Correct |
24 ms |
122712 KB |
n=500 |
41 |
Correct |
25 ms |
122764 KB |
n=500 |
42 |
Correct |
27 ms |
122712 KB |
n=500 |
43 |
Correct |
25 ms |
122712 KB |
n=500 |
44 |
Correct |
25 ms |
122764 KB |
n=500 |
45 |
Correct |
26 ms |
122724 KB |
n=500 |
46 |
Correct |
26 ms |
122924 KB |
n=500 |
47 |
Correct |
26 ms |
122968 KB |
n=500 |
48 |
Correct |
26 ms |
122716 KB |
n=500 |
49 |
Correct |
27 ms |
122712 KB |
n=500 |
50 |
Correct |
25 ms |
122712 KB |
n=500 |
51 |
Correct |
26 ms |
122716 KB |
n=500 |
52 |
Correct |
25 ms |
122716 KB |
n=500 |
53 |
Correct |
28 ms |
122980 KB |
n=500 |
54 |
Correct |
25 ms |
122716 KB |
n=500 |
55 |
Correct |
25 ms |
122716 KB |
n=278 |
56 |
Correct |
26 ms |
122716 KB |
n=500 |
57 |
Correct |
25 ms |
122716 KB |
n=500 |
58 |
Correct |
24 ms |
122716 KB |
n=500 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
122708 KB |
n=5 |
2 |
Correct |
25 ms |
122704 KB |
n=100 |
3 |
Correct |
24 ms |
122716 KB |
n=100 |
4 |
Correct |
24 ms |
122716 KB |
n=100 |
5 |
Correct |
24 ms |
122716 KB |
n=100 |
6 |
Correct |
25 ms |
122800 KB |
n=100 |
7 |
Correct |
24 ms |
122712 KB |
n=100 |
8 |
Correct |
26 ms |
122716 KB |
n=100 |
9 |
Correct |
25 ms |
122704 KB |
n=100 |
10 |
Correct |
25 ms |
122712 KB |
n=100 |
11 |
Correct |
26 ms |
122964 KB |
n=100 |
12 |
Correct |
25 ms |
122712 KB |
n=100 |
13 |
Correct |
24 ms |
122716 KB |
n=100 |
14 |
Correct |
25 ms |
122716 KB |
n=100 |
15 |
Correct |
24 ms |
122716 KB |
n=100 |
16 |
Correct |
24 ms |
122716 KB |
n=100 |
17 |
Correct |
24 ms |
122704 KB |
n=100 |
18 |
Correct |
25 ms |
122748 KB |
n=100 |
19 |
Correct |
25 ms |
122716 KB |
n=100 |
20 |
Correct |
24 ms |
122716 KB |
n=100 |
21 |
Correct |
26 ms |
122768 KB |
n=100 |
22 |
Correct |
24 ms |
122716 KB |
n=100 |
23 |
Correct |
24 ms |
122580 KB |
n=100 |
24 |
Correct |
27 ms |
122968 KB |
n=100 |
25 |
Correct |
24 ms |
122716 KB |
n=100 |
26 |
Correct |
25 ms |
122716 KB |
n=12 |
27 |
Correct |
24 ms |
122712 KB |
n=100 |
28 |
Correct |
24 ms |
122716 KB |
n=500 |
29 |
Correct |
25 ms |
122728 KB |
n=500 |
30 |
Correct |
25 ms |
122756 KB |
n=500 |
31 |
Correct |
24 ms |
122892 KB |
n=500 |
32 |
Correct |
25 ms |
122716 KB |
n=500 |
33 |
Correct |
28 ms |
122844 KB |
n=500 |
34 |
Correct |
25 ms |
122712 KB |
n=500 |
35 |
Correct |
25 ms |
122716 KB |
n=500 |
36 |
Correct |
24 ms |
122792 KB |
n=500 |
37 |
Correct |
25 ms |
122712 KB |
n=500 |
38 |
Correct |
26 ms |
122744 KB |
n=500 |
39 |
Correct |
26 ms |
122708 KB |
n=500 |
40 |
Correct |
24 ms |
122712 KB |
n=500 |
41 |
Correct |
25 ms |
122764 KB |
n=500 |
42 |
Correct |
27 ms |
122712 KB |
n=500 |
43 |
Correct |
25 ms |
122712 KB |
n=500 |
44 |
Correct |
25 ms |
122764 KB |
n=500 |
45 |
Correct |
26 ms |
122724 KB |
n=500 |
46 |
Correct |
26 ms |
122924 KB |
n=500 |
47 |
Correct |
26 ms |
122968 KB |
n=500 |
48 |
Correct |
26 ms |
122716 KB |
n=500 |
49 |
Correct |
27 ms |
122712 KB |
n=500 |
50 |
Correct |
25 ms |
122712 KB |
n=500 |
51 |
Correct |
26 ms |
122716 KB |
n=500 |
52 |
Correct |
25 ms |
122716 KB |
n=500 |
53 |
Correct |
28 ms |
122980 KB |
n=500 |
54 |
Correct |
25 ms |
122716 KB |
n=500 |
55 |
Correct |
25 ms |
122716 KB |
n=278 |
56 |
Correct |
26 ms |
122716 KB |
n=500 |
57 |
Correct |
25 ms |
122716 KB |
n=500 |
58 |
Correct |
24 ms |
122716 KB |
n=500 |
59 |
Correct |
28 ms |
122968 KB |
n=2000 |
60 |
Correct |
29 ms |
123224 KB |
n=2000 |
61 |
Correct |
29 ms |
123016 KB |
n=2000 |
62 |
Correct |
28 ms |
123164 KB |
n=2000 |
63 |
Correct |
28 ms |
122972 KB |
n=2000 |
64 |
Correct |
28 ms |
122916 KB |
n=2000 |
65 |
Correct |
29 ms |
122972 KB |
n=2000 |
66 |
Correct |
27 ms |
122972 KB |
n=2000 |
67 |
Correct |
28 ms |
122964 KB |
n=2000 |
68 |
Correct |
27 ms |
122960 KB |
n=2000 |
69 |
Correct |
27 ms |
122972 KB |
n=2000 |
70 |
Correct |
26 ms |
122968 KB |
n=2000 |
71 |
Correct |
27 ms |
122968 KB |
n=2000 |
72 |
Correct |
26 ms |
122972 KB |
n=2000 |
73 |
Correct |
26 ms |
122968 KB |
n=2000 |
74 |
Correct |
27 ms |
122948 KB |
n=1844 |
75 |
Correct |
26 ms |
122968 KB |
n=2000 |
76 |
Correct |
31 ms |
122972 KB |
n=2000 |
77 |
Correct |
28 ms |
122972 KB |
n=2000 |
78 |
Correct |
29 ms |
122912 KB |
n=2000 |
79 |
Correct |
28 ms |
122972 KB |
n=2000 |
80 |
Correct |
27 ms |
123228 KB |
n=2000 |
81 |
Correct |
28 ms |
122968 KB |
n=2000 |
82 |
Correct |
28 ms |
122972 KB |
n=2000 |
83 |
Correct |
29 ms |
123188 KB |
n=2000 |
84 |
Correct |
28 ms |
123224 KB |
n=2000 |
85 |
Correct |
27 ms |
122988 KB |
n=2000 |
86 |
Correct |
27 ms |
122972 KB |
n=2000 |
87 |
Correct |
27 ms |
122968 KB |
n=2000 |
88 |
Correct |
29 ms |
123228 KB |
n=2000 |
89 |
Correct |
28 ms |
123092 KB |
n=2000 |
90 |
Correct |
31 ms |
123216 KB |
n=2000 |
91 |
Correct |
28 ms |
123076 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
122708 KB |
n=5 |
2 |
Correct |
25 ms |
122704 KB |
n=100 |
3 |
Correct |
24 ms |
122716 KB |
n=100 |
4 |
Correct |
24 ms |
122716 KB |
n=100 |
5 |
Correct |
24 ms |
122716 KB |
n=100 |
6 |
Correct |
25 ms |
122800 KB |
n=100 |
7 |
Correct |
24 ms |
122712 KB |
n=100 |
8 |
Correct |
26 ms |
122716 KB |
n=100 |
9 |
Correct |
25 ms |
122704 KB |
n=100 |
10 |
Correct |
25 ms |
122712 KB |
n=100 |
11 |
Correct |
26 ms |
122964 KB |
n=100 |
12 |
Correct |
25 ms |
122712 KB |
n=100 |
13 |
Correct |
24 ms |
122716 KB |
n=100 |
14 |
Correct |
25 ms |
122716 KB |
n=100 |
15 |
Correct |
24 ms |
122716 KB |
n=100 |
16 |
Correct |
24 ms |
122716 KB |
n=100 |
17 |
Correct |
24 ms |
122704 KB |
n=100 |
18 |
Correct |
25 ms |
122748 KB |
n=100 |
19 |
Correct |
25 ms |
122716 KB |
n=100 |
20 |
Correct |
24 ms |
122716 KB |
n=100 |
21 |
Correct |
26 ms |
122768 KB |
n=100 |
22 |
Correct |
24 ms |
122716 KB |
n=100 |
23 |
Correct |
24 ms |
122580 KB |
n=100 |
24 |
Correct |
27 ms |
122968 KB |
n=100 |
25 |
Correct |
24 ms |
122716 KB |
n=100 |
26 |
Correct |
25 ms |
122716 KB |
n=12 |
27 |
Correct |
24 ms |
122712 KB |
n=100 |
28 |
Correct |
24 ms |
122716 KB |
n=500 |
29 |
Correct |
25 ms |
122728 KB |
n=500 |
30 |
Correct |
25 ms |
122756 KB |
n=500 |
31 |
Correct |
24 ms |
122892 KB |
n=500 |
32 |
Correct |
25 ms |
122716 KB |
n=500 |
33 |
Correct |
28 ms |
122844 KB |
n=500 |
34 |
Correct |
25 ms |
122712 KB |
n=500 |
35 |
Correct |
25 ms |
122716 KB |
n=500 |
36 |
Correct |
24 ms |
122792 KB |
n=500 |
37 |
Correct |
25 ms |
122712 KB |
n=500 |
38 |
Correct |
26 ms |
122744 KB |
n=500 |
39 |
Correct |
26 ms |
122708 KB |
n=500 |
40 |
Correct |
24 ms |
122712 KB |
n=500 |
41 |
Correct |
25 ms |
122764 KB |
n=500 |
42 |
Correct |
27 ms |
122712 KB |
n=500 |
43 |
Correct |
25 ms |
122712 KB |
n=500 |
44 |
Correct |
25 ms |
122764 KB |
n=500 |
45 |
Correct |
26 ms |
122724 KB |
n=500 |
46 |
Correct |
26 ms |
122924 KB |
n=500 |
47 |
Correct |
26 ms |
122968 KB |
n=500 |
48 |
Correct |
26 ms |
122716 KB |
n=500 |
49 |
Correct |
27 ms |
122712 KB |
n=500 |
50 |
Correct |
25 ms |
122712 KB |
n=500 |
51 |
Correct |
26 ms |
122716 KB |
n=500 |
52 |
Correct |
25 ms |
122716 KB |
n=500 |
53 |
Correct |
28 ms |
122980 KB |
n=500 |
54 |
Correct |
25 ms |
122716 KB |
n=500 |
55 |
Correct |
25 ms |
122716 KB |
n=278 |
56 |
Correct |
26 ms |
122716 KB |
n=500 |
57 |
Correct |
25 ms |
122716 KB |
n=500 |
58 |
Correct |
24 ms |
122716 KB |
n=500 |
59 |
Correct |
28 ms |
122968 KB |
n=2000 |
60 |
Correct |
29 ms |
123224 KB |
n=2000 |
61 |
Correct |
29 ms |
123016 KB |
n=2000 |
62 |
Correct |
28 ms |
123164 KB |
n=2000 |
63 |
Correct |
28 ms |
122972 KB |
n=2000 |
64 |
Correct |
28 ms |
122916 KB |
n=2000 |
65 |
Correct |
29 ms |
122972 KB |
n=2000 |
66 |
Correct |
27 ms |
122972 KB |
n=2000 |
67 |
Correct |
28 ms |
122964 KB |
n=2000 |
68 |
Correct |
27 ms |
122960 KB |
n=2000 |
69 |
Correct |
27 ms |
122972 KB |
n=2000 |
70 |
Correct |
26 ms |
122968 KB |
n=2000 |
71 |
Correct |
27 ms |
122968 KB |
n=2000 |
72 |
Correct |
26 ms |
122972 KB |
n=2000 |
73 |
Correct |
26 ms |
122968 KB |
n=2000 |
74 |
Correct |
27 ms |
122948 KB |
n=1844 |
75 |
Correct |
26 ms |
122968 KB |
n=2000 |
76 |
Correct |
31 ms |
122972 KB |
n=2000 |
77 |
Correct |
28 ms |
122972 KB |
n=2000 |
78 |
Correct |
29 ms |
122912 KB |
n=2000 |
79 |
Correct |
28 ms |
122972 KB |
n=2000 |
80 |
Correct |
27 ms |
123228 KB |
n=2000 |
81 |
Correct |
28 ms |
122968 KB |
n=2000 |
82 |
Correct |
28 ms |
122972 KB |
n=2000 |
83 |
Correct |
29 ms |
123188 KB |
n=2000 |
84 |
Correct |
28 ms |
123224 KB |
n=2000 |
85 |
Correct |
27 ms |
122988 KB |
n=2000 |
86 |
Correct |
27 ms |
122972 KB |
n=2000 |
87 |
Correct |
27 ms |
122968 KB |
n=2000 |
88 |
Correct |
29 ms |
123228 KB |
n=2000 |
89 |
Correct |
28 ms |
123092 KB |
n=2000 |
90 |
Correct |
31 ms |
123216 KB |
n=2000 |
91 |
Correct |
28 ms |
123076 KB |
n=2000 |
92 |
Correct |
695 ms |
178772 KB |
n=200000 |
93 |
Correct |
1049 ms |
185264 KB |
n=200000 |
94 |
Correct |
1104 ms |
190168 KB |
n=200000 |
95 |
Correct |
670 ms |
178700 KB |
n=200000 |
96 |
Correct |
647 ms |
178768 KB |
n=200000 |
97 |
Correct |
1142 ms |
184252 KB |
n=200000 |
98 |
Correct |
646 ms |
178672 KB |
n=200000 |
99 |
Correct |
746 ms |
178876 KB |
n=200000 |
100 |
Correct |
679 ms |
178600 KB |
n=200000 |
101 |
Correct |
960 ms |
191336 KB |
n=200000 |
102 |
Correct |
351 ms |
179808 KB |
n=200000 |
103 |
Correct |
337 ms |
179792 KB |
n=200000 |
104 |
Correct |
345 ms |
179748 KB |
n=200000 |
105 |
Correct |
341 ms |
180308 KB |
n=200000 |
106 |
Correct |
337 ms |
180248 KB |
n=200000 |
107 |
Correct |
349 ms |
180344 KB |
n=200000 |
108 |
Correct |
687 ms |
178680 KB |
n=200000 |
109 |
Correct |
661 ms |
178788 KB |
n=200000 |
110 |
Correct |
786 ms |
178776 KB |
n=200000 |
111 |
Correct |
612 ms |
178392 KB |
n=200000 |
112 |
Correct |
1101 ms |
190004 KB |
n=200000 |
113 |
Correct |
991 ms |
184072 KB |
n=200000 |
114 |
Correct |
605 ms |
178028 KB |
n=200000 |
115 |
Correct |
1068 ms |
181208 KB |
n=200000 |
116 |
Correct |
651 ms |
178784 KB |
n=200000 |
117 |
Correct |
1008 ms |
190516 KB |
n=200000 |
118 |
Correct |
1036 ms |
182832 KB |
n=200000 |
119 |
Correct |
646 ms |
178784 KB |
n=200000 |
120 |
Correct |
813 ms |
190288 KB |
n=200000 |
121 |
Correct |
877 ms |
190428 KB |
n=200000 |
122 |
Correct |
969 ms |
190812 KB |
n=200000 |
123 |
Correct |
377 ms |
180100 KB |
n=200000 |
124 |
Correct |
172 ms |
137556 KB |
n=25264 |