oj.uz

Submission #879004

# Submission time Handle Problem Language Result Execution time Memory
879004 2023-11-26T04:37:00 Z imarn Birthday gift (IZhO18_treearray) C++14
100 / 100
 923 ms 102240 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define sz(x) (int)x.size()
#define pii pair<ll,ll>
using namespace std;
const int N=2e5+5;
vector<int>g[N];
int pr[N][20],dep[N]{0};
void dfs(int u,int p,int l){
    dep[u]=l;pr[u][0]=p;
    for(int i=1;i<20;i++)pr[u][i]=pr[pr[u][i-1]][i-1];
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u,l+1);
    }
}
int lca(int a,int b){
    if(dep[a]>dep[b])swap(a,b);
    for(int i=19;i>=0;i--)if(dep[b]-(1<<i)>=dep[a])b=pr[b][i];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(pr[a][i]!=pr[b][i])a=pr[a][i],b=pr[b][i];
    return pr[a][0];
}
set<int>d[N],dd[N];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1,u,v;i<=n-1;i++)cin>>u>>v,g[u].pb(v),g[v].pb(u);
    dfs(1,1,0);int v[m+1];
    for(int i=1;i<=n;i++)d[i].insert(1e9),dd[i].insert(1e9);
    for(int i=1;i<=m;i++)cin>>v[i],dd[v[i]].insert(i);
    for(int i=1;i<=m-1;i++)d[lca(v[i],v[i+1])].insert(i);
    while(q--){
        int o;cin>>o;
        if(o==1){
            int p,x;cin>>p>>x;
            dd[v[p]].erase(dd[v[p]].lower_bound(p));
            dd[x].insert(p);
            if(p<m){
                int u = lca(v[p],v[p+1]);
                d[u].erase(d[u].lower_bound(p));
                u = lca(x,v[p+1]);
                d[u].insert(p);
            }
            if(p>1){
                int u = lca(v[p-1],v[p]);
                d[u].erase(d[u].lower_bound(p-1));
                u = lca(v[p-1],x);
                d[u].insert(p-1);
            }v[p]=x;
        }
        else {
            int l,r,v;cin>>l>>r>>v;
            auto x = dd[v].lower_bound(l);
            if(*x<=r){cout<<*x<<" "<<*x<<'\n';continue;}
            x = d[v].lower_bound(l);
            if(*x>=r)cout<<-1<<" "<<-1<<'\n';
            else cout<<*x<<" "<<(*x)+1<<'\n';
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25948 KB n=5
2 Correct 6 ms 25948 KB n=100
3 Correct 6 ms 26100 KB n=100
4 Correct 5 ms 25948 KB n=100
5 Correct 6 ms 25948 KB n=100
6 Correct 5 ms 25944 KB n=100
7 Correct 5 ms 25948 KB n=100
8 Correct 6 ms 25948 KB n=100
9 Correct 6 ms 25948 KB n=100
10 Correct 5 ms 25944 KB n=100
11 Correct 7 ms 25948 KB n=100
12 Correct 5 ms 25948 KB n=100
13 Correct 6 ms 25948 KB n=100
14 Correct 5 ms 25944 KB n=100
15 Correct 6 ms 25948 KB n=100
16 Correct 5 ms 25948 KB n=100
17 Correct 5 ms 25948 KB n=100
18 Correct 6 ms 25948 KB n=100
19 Correct 5 ms 25948 KB n=100
20 Correct 6 ms 25948 KB n=100
21 Correct 7 ms 25980 KB n=100
22 Correct 5 ms 25948 KB n=100
23 Correct 6 ms 26204 KB n=100
24 Correct 5 ms 25948 KB n=100
25 Correct 5 ms 25948 KB n=100
26 Correct 6 ms 25952 KB n=12
27 Correct 6 ms 25948 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25948 KB n=5
2 Correct 6 ms 25948 KB n=100
3 Correct 6 ms 26100 KB n=100
4 Correct 5 ms 25948 KB n=100
5 Correct 6 ms 25948 KB n=100
6 Correct 5 ms 25944 KB n=100
7 Correct 5 ms 25948 KB n=100
8 Correct 6 ms 25948 KB n=100
9 Correct 6 ms 25948 KB n=100
10 Correct 5 ms 25944 KB n=100
11 Correct 7 ms 25948 KB n=100
12 Correct 5 ms 25948 KB n=100
13 Correct 6 ms 25948 KB n=100
14 Correct 5 ms 25944 KB n=100
15 Correct 6 ms 25948 KB n=100
16 Correct 5 ms 25948 KB n=100
17 Correct 5 ms 25948 KB n=100
18 Correct 6 ms 25948 KB n=100
19 Correct 5 ms 25948 KB n=100
20 Correct 6 ms 25948 KB n=100
21 Correct 7 ms 25980 KB n=100
22 Correct 5 ms 25948 KB n=100
23 Correct 6 ms 26204 KB n=100
24 Correct 5 ms 25948 KB n=100
25 Correct 5 ms 25948 KB n=100
26 Correct 6 ms 25952 KB n=12
27 Correct 6 ms 25948 KB n=100
28 Correct 6 ms 25948 KB n=500
29 Correct 6 ms 25948 KB n=500
30 Correct 6 ms 25948 KB n=500
31 Correct 6 ms 26204 KB n=500
32 Correct 6 ms 25944 KB n=500
33 Correct 6 ms 26200 KB n=500
34 Correct 6 ms 25948 KB n=500
35 Correct 6 ms 25948 KB n=500
36 Correct 6 ms 25944 KB n=500
37 Correct 6 ms 25948 KB n=500
38 Correct 7 ms 25948 KB n=500
39 Correct 6 ms 25948 KB n=500
40 Correct 6 ms 25948 KB n=500
41 Correct 6 ms 25948 KB n=500
42 Correct 6 ms 25948 KB n=500
43 Correct 6 ms 25948 KB n=500
44 Correct 6 ms 25948 KB n=500
45 Correct 6 ms 25948 KB n=500
46 Correct 6 ms 26028 KB n=500
47 Correct 6 ms 25948 KB n=500
48 Correct 6 ms 25948 KB n=500
49 Correct 6 ms 25944 KB n=500
50 Correct 6 ms 25948 KB n=500
51 Correct 6 ms 26044 KB n=500
52 Correct 6 ms 25944 KB n=500
53 Correct 6 ms 25976 KB n=500
54 Correct 6 ms 25944 KB n=500
55 Correct 6 ms 25948 KB n=278
56 Correct 6 ms 25944 KB n=500
57 Correct 7 ms 25948 KB n=500
58 Correct 6 ms 25948 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25948 KB n=5
2 Correct 6 ms 25948 KB n=100
3 Correct 6 ms 26100 KB n=100
4 Correct 5 ms 25948 KB n=100
5 Correct 6 ms 25948 KB n=100
6 Correct 5 ms 25944 KB n=100
7 Correct 5 ms 25948 KB n=100
8 Correct 6 ms 25948 KB n=100
9 Correct 6 ms 25948 KB n=100
10 Correct 5 ms 25944 KB n=100
11 Correct 7 ms 25948 KB n=100
12 Correct 5 ms 25948 KB n=100
13 Correct 6 ms 25948 KB n=100
14 Correct 5 ms 25944 KB n=100
15 Correct 6 ms 25948 KB n=100
16 Correct 5 ms 25948 KB n=100
17 Correct 5 ms 25948 KB n=100
18 Correct 6 ms 25948 KB n=100
19 Correct 5 ms 25948 KB n=100
20 Correct 6 ms 25948 KB n=100
21 Correct 7 ms 25980 KB n=100
22 Correct 5 ms 25948 KB n=100
23 Correct 6 ms 26204 KB n=100
24 Correct 5 ms 25948 KB n=100
25 Correct 5 ms 25948 KB n=100
26 Correct 6 ms 25952 KB n=12
27 Correct 6 ms 25948 KB n=100
28 Correct 6 ms 25948 KB n=500
29 Correct 6 ms 25948 KB n=500
30 Correct 6 ms 25948 KB n=500
31 Correct 6 ms 26204 KB n=500
32 Correct 6 ms 25944 KB n=500
33 Correct 6 ms 26200 KB n=500
34 Correct 6 ms 25948 KB n=500
35 Correct 6 ms 25948 KB n=500
36 Correct 6 ms 25944 KB n=500
37 Correct 6 ms 25948 KB n=500
38 Correct 7 ms 25948 KB n=500
39 Correct 6 ms 25948 KB n=500
40 Correct 6 ms 25948 KB n=500
41 Correct 6 ms 25948 KB n=500
42 Correct 6 ms 25948 KB n=500
43 Correct 6 ms 25948 KB n=500
44 Correct 6 ms 25948 KB n=500
45 Correct 6 ms 25948 KB n=500
46 Correct 6 ms 26028 KB n=500
47 Correct 6 ms 25948 KB n=500
48 Correct 6 ms 25948 KB n=500
49 Correct 6 ms 25944 KB n=500
50 Correct 6 ms 25948 KB n=500
51 Correct 6 ms 26044 KB n=500
52 Correct 6 ms 25944 KB n=500
53 Correct 6 ms 25976 KB n=500
54 Correct 6 ms 25944 KB n=500
55 Correct 6 ms 25948 KB n=278
56 Correct 6 ms 25944 KB n=500
57 Correct 7 ms 25948 KB n=500
58 Correct 6 ms 25948 KB n=500
59 Correct 10 ms 26460 KB n=2000
60 Correct 8 ms 26460 KB n=2000
61 Correct 8 ms 26460 KB n=2000
62 Correct 8 ms 26460 KB n=2000
63 Correct 8 ms 26460 KB n=2000
64 Correct 8 ms 26460 KB n=2000
65 Correct 8 ms 26460 KB n=2000
66 Correct 8 ms 26460 KB n=2000
67 Correct 8 ms 26284 KB n=2000
68 Correct 8 ms 26460 KB n=2000
69 Correct 7 ms 26460 KB n=2000
70 Correct 8 ms 26456 KB n=2000
71 Correct 8 ms 26456 KB n=2000
72 Correct 7 ms 26460 KB n=2000
73 Correct 8 ms 26460 KB n=2000
74 Correct 7 ms 26460 KB n=1844
75 Correct 8 ms 26520 KB n=2000
76 Correct 9 ms 26460 KB n=2000
77 Correct 8 ms 26292 KB n=2000
78 Correct 8 ms 26456 KB n=2000
79 Correct 8 ms 26460 KB n=2000
80 Correct 8 ms 26452 KB n=2000
81 Correct 10 ms 26460 KB n=2000
82 Correct 9 ms 26456 KB n=2000
83 Correct 8 ms 26460 KB n=2000
84 Correct 8 ms 26460 KB n=2000
85 Correct 9 ms 26460 KB n=2000
86 Correct 9 ms 26460 KB n=2000
87 Correct 8 ms 26460 KB n=2000
88 Correct 8 ms 26460 KB n=2000
89 Correct 8 ms 26600 KB n=2000
90 Correct 9 ms 26456 KB n=2000
91 Correct 8 ms 26460 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25948 KB n=5
2 Correct 6 ms 25948 KB n=100
3 Correct 6 ms 26100 KB n=100
4 Correct 5 ms 25948 KB n=100
5 Correct 6 ms 25948 KB n=100
6 Correct 5 ms 25944 KB n=100
7 Correct 5 ms 25948 KB n=100
8 Correct 6 ms 25948 KB n=100
9 Correct 6 ms 25948 KB n=100
10 Correct 5 ms 25944 KB n=100
11 Correct 7 ms 25948 KB n=100
12 Correct 5 ms 25948 KB n=100
13 Correct 6 ms 25948 KB n=100
14 Correct 5 ms 25944 KB n=100
15 Correct 6 ms 25948 KB n=100
16 Correct 5 ms 25948 KB n=100
17 Correct 5 ms 25948 KB n=100
18 Correct 6 ms 25948 KB n=100
19 Correct 5 ms 25948 KB n=100
20 Correct 6 ms 25948 KB n=100
21 Correct 7 ms 25980 KB n=100
22 Correct 5 ms 25948 KB n=100
23 Correct 6 ms 26204 KB n=100
24 Correct 5 ms 25948 KB n=100
25 Correct 5 ms 25948 KB n=100
26 Correct 6 ms 25952 KB n=12
27 Correct 6 ms 25948 KB n=100
28 Correct 6 ms 25948 KB n=500
29 Correct 6 ms 25948 KB n=500
30 Correct 6 ms 25948 KB n=500
31 Correct 6 ms 26204 KB n=500
32 Correct 6 ms 25944 KB n=500
33 Correct 6 ms 26200 KB n=500
34 Correct 6 ms 25948 KB n=500
35 Correct 6 ms 25948 KB n=500
36 Correct 6 ms 25944 KB n=500
37 Correct 6 ms 25948 KB n=500
38 Correct 7 ms 25948 KB n=500
39 Correct 6 ms 25948 KB n=500
40 Correct 6 ms 25948 KB n=500
41 Correct 6 ms 25948 KB n=500
42 Correct 6 ms 25948 KB n=500
43 Correct 6 ms 25948 KB n=500
44 Correct 6 ms 25948 KB n=500
45 Correct 6 ms 25948 KB n=500
46 Correct 6 ms 26028 KB n=500
47 Correct 6 ms 25948 KB n=500
48 Correct 6 ms 25948 KB n=500
49 Correct 6 ms 25944 KB n=500
50 Correct 6 ms 25948 KB n=500
51 Correct 6 ms 26044 KB n=500
52 Correct 6 ms 25944 KB n=500
53 Correct 6 ms 25976 KB n=500
54 Correct 6 ms 25944 KB n=500
55 Correct 6 ms 25948 KB n=278
56 Correct 6 ms 25944 KB n=500
57 Correct 7 ms 25948 KB n=500
58 Correct 6 ms 25948 KB n=500
59 Correct 10 ms 26460 KB n=2000
60 Correct 8 ms 26460 KB n=2000
61 Correct 8 ms 26460 KB n=2000
62 Correct 8 ms 26460 KB n=2000
63 Correct 8 ms 26460 KB n=2000
64 Correct 8 ms 26460 KB n=2000
65 Correct 8 ms 26460 KB n=2000
66 Correct 8 ms 26460 KB n=2000
67 Correct 8 ms 26284 KB n=2000
68 Correct 8 ms 26460 KB n=2000
69 Correct 7 ms 26460 KB n=2000
70 Correct 8 ms 26456 KB n=2000
71 Correct 8 ms 26456 KB n=2000
72 Correct 7 ms 26460 KB n=2000
73 Correct 8 ms 26460 KB n=2000
74 Correct 7 ms 26460 KB n=1844
75 Correct 8 ms 26520 KB n=2000
76 Correct 9 ms 26460 KB n=2000
77 Correct 8 ms 26292 KB n=2000
78 Correct 8 ms 26456 KB n=2000
79 Correct 8 ms 26460 KB n=2000
80 Correct 8 ms 26452 KB n=2000
81 Correct 10 ms 26460 KB n=2000
82 Correct 9 ms 26456 KB n=2000
83 Correct 8 ms 26460 KB n=2000
84 Correct 8 ms 26460 KB n=2000
85 Correct 9 ms 26460 KB n=2000
86 Correct 9 ms 26460 KB n=2000
87 Correct 8 ms 26460 KB n=2000
88 Correct 8 ms 26460 KB n=2000
89 Correct 8 ms 26600 KB n=2000
90 Correct 9 ms 26456 KB n=2000
91 Correct 8 ms 26460 KB n=2000
92 Correct 625 ms 93264 KB n=200000
93 Correct 872 ms 97716 KB n=200000
94 Correct 843 ms 100992 KB n=200000
95 Correct 568 ms 93124 KB n=200000
96 Correct 564 ms 93376 KB n=200000
97 Correct 907 ms 96732 KB n=200000
98 Correct 548 ms 93120 KB n=200000
99 Correct 647 ms 93360 KB n=200000
100 Correct 537 ms 93364 KB n=200000
101 Correct 772 ms 102240 KB n=200000
102 Correct 349 ms 94548 KB n=200000
103 Correct 337 ms 94408 KB n=200000
104 Correct 345 ms 94292 KB n=200000
105 Correct 345 ms 94628 KB n=200000
106 Correct 340 ms 94692 KB n=200000
107 Correct 339 ms 94668 KB n=200000
108 Correct 649 ms 93040 KB n=200000
109 Correct 646 ms 93268 KB n=200000
110 Correct 677 ms 93324 KB n=200000
111 Correct 599 ms 92684 KB n=200000
112 Correct 818 ms 100956 KB n=200000
113 Correct 919 ms 96468 KB n=200000
114 Correct 628 ms 92824 KB n=200000
115 Correct 863 ms 94564 KB n=200000
116 Correct 598 ms 93452 KB n=200000
117 Correct 772 ms 101460 KB n=200000
118 Correct 923 ms 95592 KB n=200000
119 Correct 605 ms 93328 KB n=200000
120 Correct 764 ms 101120 KB n=200000
121 Correct 772 ms 101144 KB n=200000
122 Correct 723 ms 101552 KB n=200000
123 Correct 366 ms 94556 KB n=200000
124 Correct 158 ms 42664 KB n=25264