oj.uz

Submission #1118068

# Submission time Handle Problem Language Result Execution time Memory
1118068 2024-11-24T20:31:57 Z nikolashami Birthday gift (IZhO18_treearray) C++17
100 / 100
 612 ms 84808 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=2e5+4,LG=ceil(log2(N))+1;
vector<int>adj[N];
int cale[LG][N],tin[N],tout[N],ti;
int n,m,q,a[N],b[N];

void dfs(int u,int p=0){
	cale[0][u]=p;
  	for(int i=1;i<LG;++i) 
  		cale[i][u]=cale[i-1][cale[i-1][u]];
  	tin[u]=ti++;
  	for(int v:adj[u]){
  	  	if(v^p)
   			dfs(v,u);
  	}
  	tout[u]=ti++;
}

bool iznad(int u,int v){
	return tout[v]<=tout[u]&&tin[v]>=tin[u];
}

int lca(int u,int v){
	if(iznad(u,v))return u;
	if(iznad(v,u))return v;
	for(int i=LG-1;i>=0;--i){
    	if(!iznad(cale[i][v],u)&&cale[i][v])
    		v=cale[i][v];
  	}
  	return cale[0][v];
}

set<int>idA[N],idB[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>q;

    for(int i=1,u,v;i<n;++i){
    	cin>>u>>v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    tin[0]=-1e9;
    tout[0]=1e9;
    dfs(1);

    for(int i=1;i<=m;++i)
    	cin>>a[i];

    for(int i=1;i<m;++i)
    	b[i]=lca(a[i],a[i+1]);

    for(int i=1;i<=m;++i){
    	idA[a[i]].insert(i);
    	if(i<m)idB[b[i]].insert(i);
    }

    while(q--){
    	int tp;
    	cin>>tp;
    	if(tp==2){
    		int l,r,x;
    		cin>>l>>r>>x;
    		auto it1=idA[x].lower_bound(l);
    		auto it2=idB[x].lower_bound(l);
    		if(it1!=idA[x].end()&&*it1<=r)
    			cout<<*it1<<' '<<*it1<<'\n';
    		else if(it2!=idB[x].end()&&*it2<r)
    			cout<<*it2<<' '<<*it2+1<<'\n';
    		else
    			cout<<-1<<' '<<-1<<'\n';
    	}else{
    		int id,x;
    		cin>>id>>x;
    		idA[a[id]].erase(id);
    		a[id]=x;
    		idA[a[id]].insert(id);
    		if(id+1<=m){
    			idB[b[id]].erase(id);
    			b[id]=lca(a[id],a[id+1]);
    			idB[b[id]].insert(id);
    		}
    		if(id-1>=1){
    			idB[b[id-1]].erase(id-1);
    			b[id-1]=lca(a[id],a[id-1]);
    			idB[b[id-1]].insert(id-1);
    		}
    	}
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23908 KB n=5
2 Correct 15 ms 24056 KB n=100
3 Correct 15 ms 24056 KB n=100
4 Correct 16 ms 23888 KB n=100
5 Correct 15 ms 23860 KB n=100
6 Correct 16 ms 23888 KB n=100
7 Correct 16 ms 23888 KB n=100
8 Correct 16 ms 23900 KB n=100
9 Correct 16 ms 23900 KB n=100
10 Correct 17 ms 23900 KB n=100
11 Correct 16 ms 23888 KB n=100
12 Correct 16 ms 23888 KB n=100
13 Correct 16 ms 23888 KB n=100
14 Correct 16 ms 24056 KB n=100
15 Correct 16 ms 23888 KB n=100
16 Correct 16 ms 23888 KB n=100
17 Correct 16 ms 23904 KB n=100
18 Correct 16 ms 23888 KB n=100
19 Correct 20 ms 23900 KB n=100
20 Correct 17 ms 23888 KB n=100
21 Correct 20 ms 23888 KB n=100
22 Correct 18 ms 23888 KB n=100
23 Correct 20 ms 23888 KB n=100
24 Correct 17 ms 23888 KB n=100
25 Correct 17 ms 23888 KB n=100
26 Correct 18 ms 23888 KB n=12
27 Correct 16 ms 24060 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23908 KB n=5
2 Correct 15 ms 24056 KB n=100
3 Correct 15 ms 24056 KB n=100
4 Correct 16 ms 23888 KB n=100
5 Correct 15 ms 23860 KB n=100
6 Correct 16 ms 23888 KB n=100
7 Correct 16 ms 23888 KB n=100
8 Correct 16 ms 23900 KB n=100
9 Correct 16 ms 23900 KB n=100
10 Correct 17 ms 23900 KB n=100
11 Correct 16 ms 23888 KB n=100
12 Correct 16 ms 23888 KB n=100
13 Correct 16 ms 23888 KB n=100
14 Correct 16 ms 24056 KB n=100
15 Correct 16 ms 23888 KB n=100
16 Correct 16 ms 23888 KB n=100
17 Correct 16 ms 23904 KB n=100
18 Correct 16 ms 23888 KB n=100
19 Correct 20 ms 23900 KB n=100
20 Correct 17 ms 23888 KB n=100
21 Correct 20 ms 23888 KB n=100
22 Correct 18 ms 23888 KB n=100
23 Correct 20 ms 23888 KB n=100
24 Correct 17 ms 23888 KB n=100
25 Correct 17 ms 23888 KB n=100
26 Correct 18 ms 23888 KB n=12
27 Correct 16 ms 24060 KB n=100
28 Correct 19 ms 24144 KB n=500
29 Correct 18 ms 24040 KB n=500
30 Correct 18 ms 24144 KB n=500
31 Correct 17 ms 24144 KB n=500
32 Correct 19 ms 24144 KB n=500
33 Correct 17 ms 24144 KB n=500
34 Correct 17 ms 24144 KB n=500
35 Correct 18 ms 24032 KB n=500
36 Correct 18 ms 24312 KB n=500
37 Correct 22 ms 24144 KB n=500
38 Correct 19 ms 24144 KB n=500
39 Correct 18 ms 24144 KB n=500
40 Correct 18 ms 24204 KB n=500
41 Correct 18 ms 24144 KB n=500
42 Correct 18 ms 24144 KB n=500
43 Correct 19 ms 24144 KB n=500
44 Correct 22 ms 24144 KB n=500
45 Correct 18 ms 24144 KB n=500
46 Correct 18 ms 23972 KB n=500
47 Correct 17 ms 24156 KB n=500
48 Correct 18 ms 24156 KB n=500
49 Correct 18 ms 24144 KB n=500
50 Correct 22 ms 24144 KB n=500
51 Correct 17 ms 24160 KB n=500
52 Correct 20 ms 24144 KB n=500
53 Correct 19 ms 24156 KB n=500
54 Correct 19 ms 24144 KB n=500
55 Correct 20 ms 24144 KB n=278
56 Correct 16 ms 24144 KB n=500
57 Correct 16 ms 24144 KB n=500
58 Correct 17 ms 24100 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23908 KB n=5
2 Correct 15 ms 24056 KB n=100
3 Correct 15 ms 24056 KB n=100
4 Correct 16 ms 23888 KB n=100
5 Correct 15 ms 23860 KB n=100
6 Correct 16 ms 23888 KB n=100
7 Correct 16 ms 23888 KB n=100
8 Correct 16 ms 23900 KB n=100
9 Correct 16 ms 23900 KB n=100
10 Correct 17 ms 23900 KB n=100
11 Correct 16 ms 23888 KB n=100
12 Correct 16 ms 23888 KB n=100
13 Correct 16 ms 23888 KB n=100
14 Correct 16 ms 24056 KB n=100
15 Correct 16 ms 23888 KB n=100
16 Correct 16 ms 23888 KB n=100
17 Correct 16 ms 23904 KB n=100
18 Correct 16 ms 23888 KB n=100
19 Correct 20 ms 23900 KB n=100
20 Correct 17 ms 23888 KB n=100
21 Correct 20 ms 23888 KB n=100
22 Correct 18 ms 23888 KB n=100
23 Correct 20 ms 23888 KB n=100
24 Correct 17 ms 23888 KB n=100
25 Correct 17 ms 23888 KB n=100
26 Correct 18 ms 23888 KB n=12
27 Correct 16 ms 24060 KB n=100
28 Correct 19 ms 24144 KB n=500
29 Correct 18 ms 24040 KB n=500
30 Correct 18 ms 24144 KB n=500
31 Correct 17 ms 24144 KB n=500
32 Correct 19 ms 24144 KB n=500
33 Correct 17 ms 24144 KB n=500
34 Correct 17 ms 24144 KB n=500
35 Correct 18 ms 24032 KB n=500
36 Correct 18 ms 24312 KB n=500
37 Correct 22 ms 24144 KB n=500
38 Correct 19 ms 24144 KB n=500
39 Correct 18 ms 24144 KB n=500
40 Correct 18 ms 24204 KB n=500
41 Correct 18 ms 24144 KB n=500
42 Correct 18 ms 24144 KB n=500
43 Correct 19 ms 24144 KB n=500
44 Correct 22 ms 24144 KB n=500
45 Correct 18 ms 24144 KB n=500
46 Correct 18 ms 23972 KB n=500
47 Correct 17 ms 24156 KB n=500
48 Correct 18 ms 24156 KB n=500
49 Correct 18 ms 24144 KB n=500
50 Correct 22 ms 24144 KB n=500
51 Correct 17 ms 24160 KB n=500
52 Correct 20 ms 24144 KB n=500
53 Correct 19 ms 24156 KB n=500
54 Correct 19 ms 24144 KB n=500
55 Correct 20 ms 24144 KB n=278
56 Correct 16 ms 24144 KB n=500
57 Correct 16 ms 24144 KB n=500
58 Correct 17 ms 24100 KB n=500
59 Correct 18 ms 24400 KB n=2000
60 Correct 18 ms 24736 KB n=2000
61 Correct 21 ms 24400 KB n=2000
62 Correct 19 ms 24400 KB n=2000
63 Correct 21 ms 24400 KB n=2000
64 Correct 18 ms 24484 KB n=2000
65 Correct 22 ms 24360 KB n=2000
66 Correct 22 ms 24592 KB n=2000
67 Correct 21 ms 24456 KB n=2000
68 Correct 18 ms 24552 KB n=2000
69 Correct 19 ms 24416 KB n=2000
70 Correct 18 ms 24400 KB n=2000
71 Correct 22 ms 24400 KB n=2000
72 Correct 21 ms 24400 KB n=2000
73 Correct 21 ms 24648 KB n=2000
74 Correct 20 ms 24400 KB n=1844
75 Correct 19 ms 24400 KB n=2000
76 Correct 21 ms 24400 KB n=2000
77 Correct 21 ms 24648 KB n=2000
78 Correct 21 ms 24484 KB n=2000
79 Correct 21 ms 24564 KB n=2000
80 Correct 18 ms 24400 KB n=2000
81 Correct 20 ms 24400 KB n=2000
82 Correct 20 ms 24400 KB n=2000
83 Correct 21 ms 24400 KB n=2000
84 Correct 20 ms 24400 KB n=2000
85 Correct 23 ms 24396 KB n=2000
86 Correct 19 ms 24400 KB n=2000
87 Correct 19 ms 24416 KB n=2000
88 Correct 21 ms 24828 KB n=2000
89 Correct 19 ms 24656 KB n=2000
90 Correct 20 ms 24668 KB n=2000
91 Correct 19 ms 24400 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23908 KB n=5
2 Correct 15 ms 24056 KB n=100
3 Correct 15 ms 24056 KB n=100
4 Correct 16 ms 23888 KB n=100
5 Correct 15 ms 23860 KB n=100
6 Correct 16 ms 23888 KB n=100
7 Correct 16 ms 23888 KB n=100
8 Correct 16 ms 23900 KB n=100
9 Correct 16 ms 23900 KB n=100
10 Correct 17 ms 23900 KB n=100
11 Correct 16 ms 23888 KB n=100
12 Correct 16 ms 23888 KB n=100
13 Correct 16 ms 23888 KB n=100
14 Correct 16 ms 24056 KB n=100
15 Correct 16 ms 23888 KB n=100
16 Correct 16 ms 23888 KB n=100
17 Correct 16 ms 23904 KB n=100
18 Correct 16 ms 23888 KB n=100
19 Correct 20 ms 23900 KB n=100
20 Correct 17 ms 23888 KB n=100
21 Correct 20 ms 23888 KB n=100
22 Correct 18 ms 23888 KB n=100
23 Correct 20 ms 23888 KB n=100
24 Correct 17 ms 23888 KB n=100
25 Correct 17 ms 23888 KB n=100
26 Correct 18 ms 23888 KB n=12
27 Correct 16 ms 24060 KB n=100
28 Correct 19 ms 24144 KB n=500
29 Correct 18 ms 24040 KB n=500
30 Correct 18 ms 24144 KB n=500
31 Correct 17 ms 24144 KB n=500
32 Correct 19 ms 24144 KB n=500
33 Correct 17 ms 24144 KB n=500
34 Correct 17 ms 24144 KB n=500
35 Correct 18 ms 24032 KB n=500
36 Correct 18 ms 24312 KB n=500
37 Correct 22 ms 24144 KB n=500
38 Correct 19 ms 24144 KB n=500
39 Correct 18 ms 24144 KB n=500
40 Correct 18 ms 24204 KB n=500
41 Correct 18 ms 24144 KB n=500
42 Correct 18 ms 24144 KB n=500
43 Correct 19 ms 24144 KB n=500
44 Correct 22 ms 24144 KB n=500
45 Correct 18 ms 24144 KB n=500
46 Correct 18 ms 23972 KB n=500
47 Correct 17 ms 24156 KB n=500
48 Correct 18 ms 24156 KB n=500
49 Correct 18 ms 24144 KB n=500
50 Correct 22 ms 24144 KB n=500
51 Correct 17 ms 24160 KB n=500
52 Correct 20 ms 24144 KB n=500
53 Correct 19 ms 24156 KB n=500
54 Correct 19 ms 24144 KB n=500
55 Correct 20 ms 24144 KB n=278
56 Correct 16 ms 24144 KB n=500
57 Correct 16 ms 24144 KB n=500
58 Correct 17 ms 24100 KB n=500
59 Correct 18 ms 24400 KB n=2000
60 Correct 18 ms 24736 KB n=2000
61 Correct 21 ms 24400 KB n=2000
62 Correct 19 ms 24400 KB n=2000
63 Correct 21 ms 24400 KB n=2000
64 Correct 18 ms 24484 KB n=2000
65 Correct 22 ms 24360 KB n=2000
66 Correct 22 ms 24592 KB n=2000
67 Correct 21 ms 24456 KB n=2000
68 Correct 18 ms 24552 KB n=2000
69 Correct 19 ms 24416 KB n=2000
70 Correct 18 ms 24400 KB n=2000
71 Correct 22 ms 24400 KB n=2000
72 Correct 21 ms 24400 KB n=2000
73 Correct 21 ms 24648 KB n=2000
74 Correct 20 ms 24400 KB n=1844
75 Correct 19 ms 24400 KB n=2000
76 Correct 21 ms 24400 KB n=2000
77 Correct 21 ms 24648 KB n=2000
78 Correct 21 ms 24484 KB n=2000
79 Correct 21 ms 24564 KB n=2000
80 Correct 18 ms 24400 KB n=2000
81 Correct 20 ms 24400 KB n=2000
82 Correct 20 ms 24400 KB n=2000
83 Correct 21 ms 24400 KB n=2000
84 Correct 20 ms 24400 KB n=2000
85 Correct 23 ms 24396 KB n=2000
86 Correct 19 ms 24400 KB n=2000
87 Correct 19 ms 24416 KB n=2000
88 Correct 21 ms 24828 KB n=2000
89 Correct 19 ms 24656 KB n=2000
90 Correct 20 ms 24668 KB n=2000
91 Correct 19 ms 24400 KB n=2000
92 Correct 499 ms 75296 KB n=200000
93 Correct 488 ms 80204 KB n=200000
94 Correct 426 ms 83552 KB n=200000
95 Correct 504 ms 75232 KB n=200000
96 Correct 490 ms 75296 KB n=200000
97 Correct 433 ms 79484 KB n=200000
98 Correct 473 ms 75196 KB n=200000
99 Correct 571 ms 75500 KB n=200000
100 Correct 518 ms 75200 KB n=200000
101 Correct 371 ms 84808 KB n=200000
102 Correct 283 ms 76360 KB n=200000
103 Correct 272 ms 76360 KB n=200000
104 Correct 281 ms 76436 KB n=200000
105 Correct 275 ms 76732 KB n=200000
106 Correct 290 ms 76680 KB n=200000
107 Correct 296 ms 76788 KB n=200000
108 Correct 493 ms 75364 KB n=200000
109 Correct 514 ms 75336 KB n=200000
110 Correct 488 ms 75328 KB n=200000
111 Correct 538 ms 74556 KB n=200000
112 Correct 334 ms 83768 KB n=200000
113 Correct 438 ms 79448 KB n=200000
114 Correct 506 ms 74716 KB n=200000
115 Correct 612 ms 77156 KB n=200000
116 Correct 504 ms 75444 KB n=200000
117 Correct 379 ms 84120 KB n=200000
118 Correct 584 ms 78096 KB n=200000
119 Correct 490 ms 75252 KB n=200000
120 Correct 376 ms 83784 KB n=200000
121 Correct 416 ms 83784 KB n=200000
122 Correct 347 ms 84040 KB n=200000
123 Correct 334 ms 76548 KB n=200000
124 Correct 121 ms 39240 KB n=25264