oj.uz

Submission #1037328

# Submission time Handle Problem Language Result Execution time Memory
1037328 2024-07-28T14:05:04 Z goduadzesaba Birthday gift (IZhO18_treearray) C++17
0 / 100
 4 ms 29528 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fr first
#define sc second
const int N=2e5+5,mod=1e9+7;
int t,n,m,q,x,y,z,a1,a2,cur,tin[N],tout[N],par[N][20],a[N],b[N];
vector <int> v[N]; set <int> s1[N],s2[N];
void dfs (int g,int p){
	cur++; tin[g]=cur;
	par[g][0]=p;
	for (int i=1; i<20; i++)
		par[g][i]=par[par[g][i-1]][i-1];
	for (int i:v[g]){
		if (i==p) continue;
		dfs(i,g);
	}
	tout[g]=cur;
}
bool ispar(int a,int b){
	if (tin[a]<=tin[b] && tout[a]>=tout[b])
		return 1;
	return 0;
}
int lca(int a,int b){
	if (ispar(a,b)) return a;
	for (int i=19; i>=0; i--)
		if (par[a][i]>0 && !ispar(par[a][i],b))
			a=par[a][i];
	return par[a][0];
}
signed main(){
    ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>q;
	for (int i=1; i<n; i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	for (int i=1; i<=m; i++){
		cin>>a[i];
		s1[a[i]].insert(i);
	}
	for (int i=1; i<m; i++){
		b[i]=lca(a[i],a[i+1]);
		s2[b[i]].insert(i);
	}
	while (q--){
		cin>>t;
		if (t==1){
			cin>>x>>y;
			s1[a[x]].erase(x);
			a[x]=y;
			s1[a[x]].insert(x);
			if (x<m){
				s2[b[x]].erase(x);
				b[x]=lca(a[x],a[x+1]);
				s2[b[x]].insert(x);
			}
			if (x>1){
				s2[b[x-1]].erase(x-1);
				b[x-1]=lca(a[x-1],a[x]);
				s2[b[x-1]].insert(x-1);
			}
		}
		else{
			cin>>x>>y>>z;
			a1=a2=n+1;
			if (s1[z].lower_bound(x)!=s1[z].end())
				a1=*s1[z].lower_bound(x);
			if (s2[z].lower_bound(x)!=s2[z].end())
				a2=*s2[z].lower_bound(x);
			if (a1<=y) cout<<a1<<" "<<a1;
			else if (a2<y) cout<<a2<<" "<<a2+1;
			else cout<<"-1 -1";
			cout<<"\n";
		}
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB n=5
2 Correct 4 ms 29276 KB n=100
3 Correct 4 ms 29276 KB n=100
4 Correct 4 ms 29528 KB n=100
5 Correct 3 ms 29276 KB n=100
6 Correct 4 ms 29276 KB n=100
7 Correct 4 ms 29276 KB n=100
8 Correct 4 ms 29276 KB n=100
9 Correct 4 ms 29272 KB n=100
10 Correct 4 ms 29276 KB n=100
11 Correct 4 ms 29276 KB n=100
12 Correct 4 ms 29276 KB n=100
13 Correct 4 ms 29276 KB n=100
14 Correct 4 ms 29288 KB n=100
15 Correct 4 ms 29276 KB n=100
16 Correct 4 ms 29276 KB n=100
17 Correct 3 ms 29276 KB n=100
18 Correct 4 ms 29276 KB n=100
19 Correct 4 ms 29372 KB n=100
20 Correct 4 ms 29276 KB n=100
21 Correct 4 ms 29352 KB n=100
22 Correct 4 ms 29356 KB n=100
23 Correct 4 ms 29276 KB n=100
24 Correct 4 ms 29324 KB n=100
25 Correct 4 ms 29276 KB n=100
26 Incorrect 4 ms 29276 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB n=5
2 Correct 4 ms 29276 KB n=100
3 Correct 4 ms 29276 KB n=100
4 Correct 4 ms 29528 KB n=100
5 Correct 3 ms 29276 KB n=100
6 Correct 4 ms 29276 KB n=100
7 Correct 4 ms 29276 KB n=100
8 Correct 4 ms 29276 KB n=100
9 Correct 4 ms 29272 KB n=100
10 Correct 4 ms 29276 KB n=100
11 Correct 4 ms 29276 KB n=100
12 Correct 4 ms 29276 KB n=100
13 Correct 4 ms 29276 KB n=100
14 Correct 4 ms 29288 KB n=100
15 Correct 4 ms 29276 KB n=100
16 Correct 4 ms 29276 KB n=100
17 Correct 3 ms 29276 KB n=100
18 Correct 4 ms 29276 KB n=100
19 Correct 4 ms 29372 KB n=100
20 Correct 4 ms 29276 KB n=100
21 Correct 4 ms 29352 KB n=100
22 Correct 4 ms 29356 KB n=100
23 Correct 4 ms 29276 KB n=100
24 Correct 4 ms 29324 KB n=100
25 Correct 4 ms 29276 KB n=100
26 Incorrect 4 ms 29276 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB n=5
2 Correct 4 ms 29276 KB n=100
3 Correct 4 ms 29276 KB n=100
4 Correct 4 ms 29528 KB n=100
5 Correct 3 ms 29276 KB n=100
6 Correct 4 ms 29276 KB n=100
7 Correct 4 ms 29276 KB n=100
8 Correct 4 ms 29276 KB n=100
9 Correct 4 ms 29272 KB n=100
10 Correct 4 ms 29276 KB n=100
11 Correct 4 ms 29276 KB n=100
12 Correct 4 ms 29276 KB n=100
13 Correct 4 ms 29276 KB n=100
14 Correct 4 ms 29288 KB n=100
15 Correct 4 ms 29276 KB n=100
16 Correct 4 ms 29276 KB n=100
17 Correct 3 ms 29276 KB n=100
18 Correct 4 ms 29276 KB n=100
19 Correct 4 ms 29372 KB n=100
20 Correct 4 ms 29276 KB n=100
21 Correct 4 ms 29352 KB n=100
22 Correct 4 ms 29356 KB n=100
23 Correct 4 ms 29276 KB n=100
24 Correct 4 ms 29324 KB n=100
25 Correct 4 ms 29276 KB n=100
26 Incorrect 4 ms 29276 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29272 KB n=5
2 Correct 4 ms 29276 KB n=100
3 Correct 4 ms 29276 KB n=100
4 Correct 4 ms 29528 KB n=100
5 Correct 3 ms 29276 KB n=100
6 Correct 4 ms 29276 KB n=100
7 Correct 4 ms 29276 KB n=100
8 Correct 4 ms 29276 KB n=100
9 Correct 4 ms 29272 KB n=100
10 Correct 4 ms 29276 KB n=100
11 Correct 4 ms 29276 KB n=100
12 Correct 4 ms 29276 KB n=100
13 Correct 4 ms 29276 KB n=100
14 Correct 4 ms 29288 KB n=100
15 Correct 4 ms 29276 KB n=100
16 Correct 4 ms 29276 KB n=100
17 Correct 3 ms 29276 KB n=100
18 Correct 4 ms 29276 KB n=100
19 Correct 4 ms 29372 KB n=100
20 Correct 4 ms 29276 KB n=100
21 Correct 4 ms 29352 KB n=100
22 Correct 4 ms 29356 KB n=100
23 Correct 4 ms 29276 KB n=100
24 Correct 4 ms 29324 KB n=100
25 Correct 4 ms 29276 KB n=100
26 Incorrect 4 ms 29276 KB Wrong output format.
27 Halted 0 ms 0 KB -