Submission #683814

#	Time	Username	Problem	Language	Result	Execution time	Memory
683814		luka1234	Birthday gift (IZhO18_treearray)	C++14	100 / 100	860 ms	87040 KiB

treearray

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define db double
using namespace std;
int n,m,q;
int a[200001];
vector<int> g[200001];
int A[200001][21];
int p[200001];
int tin[200001],tout[200001];
int timer=0;
int lcas[200001];
set<int> s[200001];
set<int> s2[200001];
set<int>::iterator it;
void dfs(int v,int e){
	p[v]=e;
	tin[v]=++timer;
	for(int i:g[v]){
		if(i!=e){
			dfs(i,v);
		}
	}
	tout[v]=++timer;
}
void prepare(){
	for(int i=1;i<=n;i++){
		A[i][0]=p[i];
		for(int k=1;k<=20;k++){
			A[i][k]=-1;
		}
	}
	for(int k=1;k<=20;k++){
		for(int i=1;i<=n;i++){
			if(A[i][k]==-1){
				if(A[i][k-1]!=-1){
					A[i][k]=A[A[i][k-1]][k-1];
				}
			}
		}
	}
}
bool isancestor(int u,int v){
	return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
int lca(int x,int y){
	if(isancestor(x,y))
	   return x;
	if(isancestor(y,x))
	   return y;
	for(int k=20;k>=0;k--){
		if(A[x][k]==-1) 
		   continue;
		if(!isancestor(A[x][k],y)){
			x=A[x][k];
		}
	}
	return p[x];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>q;
	for(int k=1;k<n;k++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int k=1;k<=m;k++){
		cin>>a[k];
		s2[a[k]].insert(k);
	}
	dfs(1,-1);
	prepare();
	for(int k=1;k<m;k++){
		int f=lca(a[k],a[k+1]);
		lcas[k]=f;
		s[f].insert(k);
	}
	while(q--){
		int ind;
		cin>>ind;
		if(ind==2){
			int x,y,z;
			cin>>x>>y>>z;
			it=s2[z].lower_bound(x);
			if(it!=s2[z].end()){
				int f1=*it;
				if(f1<=y){
					cout<<f1<<' '<<f1<<"\n";
					continue;
				}
			}
			it=s[z].lower_bound(x);
			if(it==s[z].end()){
				cout<<-1<<' '<<-1<<"\n";
				continue;
			}
			int f=*it;
			if(f>(y-1)){
				cout<<-1<<' '<<-1<<"\n";
				continue;
			}
			cout<<f<<' '<<f+1<<"\n";
		}
		else{
			int x,y;
			cin>>x>>y;
			s2[a[x]].erase(x);
			s2[y].insert(x);
			a[x]=y;
			if(x>1){
				int prev=lcas[x-1];
				s[prev].erase(x-1);
				int cur=lca(a[x-1],a[x]);
				s[cur].insert(x-1);
				lcas[x-1]=cur;
			}
			if(x<m){
				int prev=lcas[x];
				s[prev].erase(x);
				int cur=lca(a[x],a[x+1]);
				s[cur].insert(x);
				lcas[x]=cur;
			}
		}
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44