#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,q;
vector<ll> g[maxN];
ll P[maxN][19],h[maxN];
void dfs(ll u=1,ll p=1)
{
P[u][0]=p;
for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
for(int v:g[u])
{
if(v!=p)
{
h[v]=h[u]+1;
dfs(v,u);
}
}
}
ll a[maxN];
set<int> s[maxN];
ll lca(ll u,ll v)
{
if(h[u]<h[v]) swap(u,v);
for(int i=18;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
if(u==v) return u;
for(int i=18;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
return P[u][0];
}
set<int> ss[maxN];
void solve()
{
cin >> n >> m >> q;
for(int i=1;i<n;i++)
{
ll u,v;
cin >> u >> v ;
g[u].pb(v);
g[v].pb(u);
}
dfs();
for(int i=1;i<=m;i++)
{
cin >> a[i];
if(i>1)
{
s[lca(a[i],a[i-1])].insert(i);
}
ss[a[i]].insert(i);
}
for(int tt=1;tt<=q;tt++)
{
ll t;
cin >> t;
if(t==1)
{
ll i,val;
cin >> i >> val;
ss[a[i]].erase(i);
ss[val].insert(i);
if(i>1)
{
s[lca(a[i],a[i-1])].erase(i);
s[lca(val,a[i-1])].insert(i);
}
if(i<m)
{
s[lca(a[i],a[i+1])].erase(i+1);
s[lca(val,a[i+1])].insert(i+1);
}
a[i]=val;
}
else
{
ll l,r,v;
cin >> l >> r >> v;
auto cc=s[v].upper_bound(l);
if(cc!=s[v].end()&&*cc<=r)
{
cout << *cc-1<<' '<<*cc<<'\n';
}
else
{
cc=ss[v].lower_bound(l);
if(cc!=ss[v].end()&&*cc<=r)
{
cout << *cc<<' '<<*cc<<'\n';
}
else cout << -1 <<' '<<-1<<'\n';
}
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23764 KB |
n=5 |
2 |
Correct |
11 ms |
23764 KB |
n=100 |
3 |
Correct |
11 ms |
23852 KB |
n=100 |
4 |
Correct |
11 ms |
23840 KB |
n=100 |
5 |
Correct |
11 ms |
23764 KB |
n=100 |
6 |
Correct |
11 ms |
23848 KB |
n=100 |
7 |
Correct |
11 ms |
23764 KB |
n=100 |
8 |
Correct |
11 ms |
23764 KB |
n=100 |
9 |
Correct |
11 ms |
23764 KB |
n=100 |
10 |
Correct |
12 ms |
23732 KB |
n=100 |
11 |
Correct |
11 ms |
23832 KB |
n=100 |
12 |
Correct |
11 ms |
23736 KB |
n=100 |
13 |
Correct |
11 ms |
23764 KB |
n=100 |
14 |
Correct |
12 ms |
23840 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23756 KB |
n=100 |
18 |
Correct |
12 ms |
23780 KB |
n=100 |
19 |
Correct |
11 ms |
23764 KB |
n=100 |
20 |
Correct |
11 ms |
23852 KB |
n=100 |
21 |
Correct |
11 ms |
23764 KB |
n=100 |
22 |
Correct |
12 ms |
23752 KB |
n=100 |
23 |
Correct |
12 ms |
23808 KB |
n=100 |
24 |
Correct |
14 ms |
23828 KB |
n=100 |
25 |
Correct |
11 ms |
23764 KB |
n=100 |
26 |
Correct |
11 ms |
23764 KB |
n=12 |
27 |
Correct |
11 ms |
23764 KB |
n=100 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23764 KB |
n=5 |
2 |
Correct |
11 ms |
23764 KB |
n=100 |
3 |
Correct |
11 ms |
23852 KB |
n=100 |
4 |
Correct |
11 ms |
23840 KB |
n=100 |
5 |
Correct |
11 ms |
23764 KB |
n=100 |
6 |
Correct |
11 ms |
23848 KB |
n=100 |
7 |
Correct |
11 ms |
23764 KB |
n=100 |
8 |
Correct |
11 ms |
23764 KB |
n=100 |
9 |
Correct |
11 ms |
23764 KB |
n=100 |
10 |
Correct |
12 ms |
23732 KB |
n=100 |
11 |
Correct |
11 ms |
23832 KB |
n=100 |
12 |
Correct |
11 ms |
23736 KB |
n=100 |
13 |
Correct |
11 ms |
23764 KB |
n=100 |
14 |
Correct |
12 ms |
23840 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23756 KB |
n=100 |
18 |
Correct |
12 ms |
23780 KB |
n=100 |
19 |
Correct |
11 ms |
23764 KB |
n=100 |
20 |
Correct |
11 ms |
23852 KB |
n=100 |
21 |
Correct |
11 ms |
23764 KB |
n=100 |
22 |
Correct |
12 ms |
23752 KB |
n=100 |
23 |
Correct |
12 ms |
23808 KB |
n=100 |
24 |
Correct |
14 ms |
23828 KB |
n=100 |
25 |
Correct |
11 ms |
23764 KB |
n=100 |
26 |
Correct |
11 ms |
23764 KB |
n=12 |
27 |
Correct |
11 ms |
23764 KB |
n=100 |
28 |
Correct |
12 ms |
23948 KB |
n=500 |
29 |
Correct |
13 ms |
23892 KB |
n=500 |
30 |
Correct |
12 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23892 KB |
n=500 |
32 |
Correct |
13 ms |
23908 KB |
n=500 |
33 |
Correct |
12 ms |
23892 KB |
n=500 |
34 |
Correct |
13 ms |
23892 KB |
n=500 |
35 |
Correct |
12 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
12 ms |
23980 KB |
n=500 |
38 |
Correct |
13 ms |
23880 KB |
n=500 |
39 |
Correct |
12 ms |
23892 KB |
n=500 |
40 |
Correct |
12 ms |
23892 KB |
n=500 |
41 |
Correct |
12 ms |
23892 KB |
n=500 |
42 |
Correct |
12 ms |
23892 KB |
n=500 |
43 |
Correct |
12 ms |
23892 KB |
n=500 |
44 |
Correct |
12 ms |
23968 KB |
n=500 |
45 |
Correct |
14 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
23892 KB |
n=500 |
47 |
Correct |
12 ms |
23892 KB |
n=500 |
48 |
Correct |
11 ms |
23892 KB |
n=500 |
49 |
Correct |
12 ms |
23892 KB |
n=500 |
50 |
Correct |
14 ms |
23916 KB |
n=500 |
51 |
Correct |
12 ms |
23892 KB |
n=500 |
52 |
Correct |
12 ms |
23952 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
12 ms |
23988 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
12 ms |
23892 KB |
n=500 |
57 |
Correct |
12 ms |
24020 KB |
n=500 |
58 |
Correct |
12 ms |
23868 KB |
n=500 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23764 KB |
n=5 |
2 |
Correct |
11 ms |
23764 KB |
n=100 |
3 |
Correct |
11 ms |
23852 KB |
n=100 |
4 |
Correct |
11 ms |
23840 KB |
n=100 |
5 |
Correct |
11 ms |
23764 KB |
n=100 |
6 |
Correct |
11 ms |
23848 KB |
n=100 |
7 |
Correct |
11 ms |
23764 KB |
n=100 |
8 |
Correct |
11 ms |
23764 KB |
n=100 |
9 |
Correct |
11 ms |
23764 KB |
n=100 |
10 |
Correct |
12 ms |
23732 KB |
n=100 |
11 |
Correct |
11 ms |
23832 KB |
n=100 |
12 |
Correct |
11 ms |
23736 KB |
n=100 |
13 |
Correct |
11 ms |
23764 KB |
n=100 |
14 |
Correct |
12 ms |
23840 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23756 KB |
n=100 |
18 |
Correct |
12 ms |
23780 KB |
n=100 |
19 |
Correct |
11 ms |
23764 KB |
n=100 |
20 |
Correct |
11 ms |
23852 KB |
n=100 |
21 |
Correct |
11 ms |
23764 KB |
n=100 |
22 |
Correct |
12 ms |
23752 KB |
n=100 |
23 |
Correct |
12 ms |
23808 KB |
n=100 |
24 |
Correct |
14 ms |
23828 KB |
n=100 |
25 |
Correct |
11 ms |
23764 KB |
n=100 |
26 |
Correct |
11 ms |
23764 KB |
n=12 |
27 |
Correct |
11 ms |
23764 KB |
n=100 |
28 |
Correct |
12 ms |
23948 KB |
n=500 |
29 |
Correct |
13 ms |
23892 KB |
n=500 |
30 |
Correct |
12 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23892 KB |
n=500 |
32 |
Correct |
13 ms |
23908 KB |
n=500 |
33 |
Correct |
12 ms |
23892 KB |
n=500 |
34 |
Correct |
13 ms |
23892 KB |
n=500 |
35 |
Correct |
12 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
12 ms |
23980 KB |
n=500 |
38 |
Correct |
13 ms |
23880 KB |
n=500 |
39 |
Correct |
12 ms |
23892 KB |
n=500 |
40 |
Correct |
12 ms |
23892 KB |
n=500 |
41 |
Correct |
12 ms |
23892 KB |
n=500 |
42 |
Correct |
12 ms |
23892 KB |
n=500 |
43 |
Correct |
12 ms |
23892 KB |
n=500 |
44 |
Correct |
12 ms |
23968 KB |
n=500 |
45 |
Correct |
14 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
23892 KB |
n=500 |
47 |
Correct |
12 ms |
23892 KB |
n=500 |
48 |
Correct |
11 ms |
23892 KB |
n=500 |
49 |
Correct |
12 ms |
23892 KB |
n=500 |
50 |
Correct |
14 ms |
23916 KB |
n=500 |
51 |
Correct |
12 ms |
23892 KB |
n=500 |
52 |
Correct |
12 ms |
23952 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
12 ms |
23988 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
12 ms |
23892 KB |
n=500 |
57 |
Correct |
12 ms |
24020 KB |
n=500 |
58 |
Correct |
12 ms |
23868 KB |
n=500 |
59 |
Correct |
14 ms |
24404 KB |
n=2000 |
60 |
Correct |
14 ms |
24444 KB |
n=2000 |
61 |
Correct |
14 ms |
24372 KB |
n=2000 |
62 |
Correct |
15 ms |
24404 KB |
n=2000 |
63 |
Correct |
14 ms |
24392 KB |
n=2000 |
64 |
Correct |
14 ms |
24456 KB |
n=2000 |
65 |
Correct |
16 ms |
24384 KB |
n=2000 |
66 |
Correct |
14 ms |
24404 KB |
n=2000 |
67 |
Correct |
17 ms |
24416 KB |
n=2000 |
68 |
Correct |
16 ms |
24456 KB |
n=2000 |
69 |
Correct |
14 ms |
24392 KB |
n=2000 |
70 |
Correct |
16 ms |
24376 KB |
n=2000 |
71 |
Correct |
13 ms |
24408 KB |
n=2000 |
72 |
Correct |
14 ms |
24404 KB |
n=2000 |
73 |
Correct |
15 ms |
24404 KB |
n=2000 |
74 |
Correct |
14 ms |
24276 KB |
n=1844 |
75 |
Correct |
13 ms |
24336 KB |
n=2000 |
76 |
Correct |
16 ms |
24428 KB |
n=2000 |
77 |
Correct |
16 ms |
24404 KB |
n=2000 |
78 |
Correct |
14 ms |
24404 KB |
n=2000 |
79 |
Correct |
14 ms |
24380 KB |
n=2000 |
80 |
Correct |
14 ms |
24476 KB |
n=2000 |
81 |
Correct |
14 ms |
24404 KB |
n=2000 |
82 |
Correct |
16 ms |
24404 KB |
n=2000 |
83 |
Correct |
13 ms |
24404 KB |
n=2000 |
84 |
Correct |
15 ms |
24532 KB |
n=2000 |
85 |
Correct |
14 ms |
24416 KB |
n=2000 |
86 |
Correct |
14 ms |
24404 KB |
n=2000 |
87 |
Correct |
14 ms |
24404 KB |
n=2000 |
88 |
Correct |
13 ms |
24404 KB |
n=2000 |
89 |
Correct |
14 ms |
24400 KB |
n=2000 |
90 |
Correct |
14 ms |
24404 KB |
n=2000 |
91 |
Correct |
14 ms |
24344 KB |
n=2000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
23764 KB |
n=5 |
2 |
Correct |
11 ms |
23764 KB |
n=100 |
3 |
Correct |
11 ms |
23852 KB |
n=100 |
4 |
Correct |
11 ms |
23840 KB |
n=100 |
5 |
Correct |
11 ms |
23764 KB |
n=100 |
6 |
Correct |
11 ms |
23848 KB |
n=100 |
7 |
Correct |
11 ms |
23764 KB |
n=100 |
8 |
Correct |
11 ms |
23764 KB |
n=100 |
9 |
Correct |
11 ms |
23764 KB |
n=100 |
10 |
Correct |
12 ms |
23732 KB |
n=100 |
11 |
Correct |
11 ms |
23832 KB |
n=100 |
12 |
Correct |
11 ms |
23736 KB |
n=100 |
13 |
Correct |
11 ms |
23764 KB |
n=100 |
14 |
Correct |
12 ms |
23840 KB |
n=100 |
15 |
Correct |
11 ms |
23764 KB |
n=100 |
16 |
Correct |
12 ms |
23764 KB |
n=100 |
17 |
Correct |
12 ms |
23756 KB |
n=100 |
18 |
Correct |
12 ms |
23780 KB |
n=100 |
19 |
Correct |
11 ms |
23764 KB |
n=100 |
20 |
Correct |
11 ms |
23852 KB |
n=100 |
21 |
Correct |
11 ms |
23764 KB |
n=100 |
22 |
Correct |
12 ms |
23752 KB |
n=100 |
23 |
Correct |
12 ms |
23808 KB |
n=100 |
24 |
Correct |
14 ms |
23828 KB |
n=100 |
25 |
Correct |
11 ms |
23764 KB |
n=100 |
26 |
Correct |
11 ms |
23764 KB |
n=12 |
27 |
Correct |
11 ms |
23764 KB |
n=100 |
28 |
Correct |
12 ms |
23948 KB |
n=500 |
29 |
Correct |
13 ms |
23892 KB |
n=500 |
30 |
Correct |
12 ms |
23892 KB |
n=500 |
31 |
Correct |
12 ms |
23892 KB |
n=500 |
32 |
Correct |
13 ms |
23908 KB |
n=500 |
33 |
Correct |
12 ms |
23892 KB |
n=500 |
34 |
Correct |
13 ms |
23892 KB |
n=500 |
35 |
Correct |
12 ms |
23892 KB |
n=500 |
36 |
Correct |
12 ms |
23892 KB |
n=500 |
37 |
Correct |
12 ms |
23980 KB |
n=500 |
38 |
Correct |
13 ms |
23880 KB |
n=500 |
39 |
Correct |
12 ms |
23892 KB |
n=500 |
40 |
Correct |
12 ms |
23892 KB |
n=500 |
41 |
Correct |
12 ms |
23892 KB |
n=500 |
42 |
Correct |
12 ms |
23892 KB |
n=500 |
43 |
Correct |
12 ms |
23892 KB |
n=500 |
44 |
Correct |
12 ms |
23968 KB |
n=500 |
45 |
Correct |
14 ms |
23892 KB |
n=500 |
46 |
Correct |
12 ms |
23892 KB |
n=500 |
47 |
Correct |
12 ms |
23892 KB |
n=500 |
48 |
Correct |
11 ms |
23892 KB |
n=500 |
49 |
Correct |
12 ms |
23892 KB |
n=500 |
50 |
Correct |
14 ms |
23916 KB |
n=500 |
51 |
Correct |
12 ms |
23892 KB |
n=500 |
52 |
Correct |
12 ms |
23952 KB |
n=500 |
53 |
Correct |
12 ms |
23892 KB |
n=500 |
54 |
Correct |
12 ms |
23988 KB |
n=500 |
55 |
Correct |
12 ms |
23892 KB |
n=278 |
56 |
Correct |
12 ms |
23892 KB |
n=500 |
57 |
Correct |
12 ms |
24020 KB |
n=500 |
58 |
Correct |
12 ms |
23868 KB |
n=500 |
59 |
Correct |
14 ms |
24404 KB |
n=2000 |
60 |
Correct |
14 ms |
24444 KB |
n=2000 |
61 |
Correct |
14 ms |
24372 KB |
n=2000 |
62 |
Correct |
15 ms |
24404 KB |
n=2000 |
63 |
Correct |
14 ms |
24392 KB |
n=2000 |
64 |
Correct |
14 ms |
24456 KB |
n=2000 |
65 |
Correct |
16 ms |
24384 KB |
n=2000 |
66 |
Correct |
14 ms |
24404 KB |
n=2000 |
67 |
Correct |
17 ms |
24416 KB |
n=2000 |
68 |
Correct |
16 ms |
24456 KB |
n=2000 |
69 |
Correct |
14 ms |
24392 KB |
n=2000 |
70 |
Correct |
16 ms |
24376 KB |
n=2000 |
71 |
Correct |
13 ms |
24408 KB |
n=2000 |
72 |
Correct |
14 ms |
24404 KB |
n=2000 |
73 |
Correct |
15 ms |
24404 KB |
n=2000 |
74 |
Correct |
14 ms |
24276 KB |
n=1844 |
75 |
Correct |
13 ms |
24336 KB |
n=2000 |
76 |
Correct |
16 ms |
24428 KB |
n=2000 |
77 |
Correct |
16 ms |
24404 KB |
n=2000 |
78 |
Correct |
14 ms |
24404 KB |
n=2000 |
79 |
Correct |
14 ms |
24380 KB |
n=2000 |
80 |
Correct |
14 ms |
24476 KB |
n=2000 |
81 |
Correct |
14 ms |
24404 KB |
n=2000 |
82 |
Correct |
16 ms |
24404 KB |
n=2000 |
83 |
Correct |
13 ms |
24404 KB |
n=2000 |
84 |
Correct |
15 ms |
24532 KB |
n=2000 |
85 |
Correct |
14 ms |
24416 KB |
n=2000 |
86 |
Correct |
14 ms |
24404 KB |
n=2000 |
87 |
Correct |
14 ms |
24404 KB |
n=2000 |
88 |
Correct |
13 ms |
24404 KB |
n=2000 |
89 |
Correct |
14 ms |
24400 KB |
n=2000 |
90 |
Correct |
14 ms |
24404 KB |
n=2000 |
91 |
Correct |
14 ms |
24344 KB |
n=2000 |
92 |
Correct |
690 ms |
84676 KB |
n=200000 |
93 |
Correct |
1028 ms |
88356 KB |
n=200000 |
94 |
Correct |
965 ms |
91248 KB |
n=200000 |
95 |
Correct |
682 ms |
84352 KB |
n=200000 |
96 |
Correct |
698 ms |
84276 KB |
n=200000 |
97 |
Correct |
1087 ms |
87300 KB |
n=200000 |
98 |
Correct |
802 ms |
84284 KB |
n=200000 |
99 |
Correct |
990 ms |
83884 KB |
n=200000 |
100 |
Correct |
728 ms |
84364 KB |
n=200000 |
101 |
Correct |
952 ms |
91992 KB |
n=200000 |
102 |
Correct |
422 ms |
85548 KB |
n=200000 |
103 |
Correct |
418 ms |
85536 KB |
n=200000 |
104 |
Correct |
430 ms |
85580 KB |
n=200000 |
105 |
Correct |
434 ms |
85452 KB |
n=200000 |
106 |
Correct |
427 ms |
85232 KB |
n=200000 |
107 |
Correct |
426 ms |
85224 KB |
n=200000 |
108 |
Correct |
770 ms |
84172 KB |
n=200000 |
109 |
Correct |
806 ms |
84252 KB |
n=200000 |
110 |
Correct |
796 ms |
84236 KB |
n=200000 |
111 |
Correct |
675 ms |
84284 KB |
n=200000 |
112 |
Correct |
968 ms |
91260 KB |
n=200000 |
113 |
Correct |
1054 ms |
87404 KB |
n=200000 |
114 |
Correct |
691 ms |
84376 KB |
n=200000 |
115 |
Correct |
1130 ms |
85364 KB |
n=200000 |
116 |
Correct |
659 ms |
84000 KB |
n=200000 |
117 |
Correct |
984 ms |
91472 KB |
n=200000 |
118 |
Correct |
1083 ms |
86188 KB |
n=200000 |
119 |
Correct |
638 ms |
84084 KB |
n=200000 |
120 |
Correct |
914 ms |
91892 KB |
n=200000 |
121 |
Correct |
925 ms |
91636 KB |
n=200000 |
122 |
Correct |
915 ms |
92212 KB |
n=200000 |
123 |
Correct |
448 ms |
84904 KB |
n=200000 |
124 |
Correct |
218 ms |
39056 KB |
n=25264 |