Submission #312510

#	Time	Username	Problem	Language	Result	Execution time	Memory
312510		mosiashvililuka	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1506 ms	84868 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],lf[200009],rg[200009],tim,msh[200009][20],tp,pas1,pas2;
vector <int> v[200009];
set <int> s[200009],ss[200009];
set <int>::iterator it;
void dfs(int q, int w){
	tim++;
	lf[q]=rg[q]=tim;
	msh[q][0]=w;
	for(int h=1; h<=18; h++){
		msh[q][h]=msh[msh[q][h-1]][h-1];
	}
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
		if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
	}
}
bool anc(int q, int w){
	if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int lca(int q, int w){
	if(anc(q,w)) return q;
	if(anc(w,q)) return w;
	for(int h=18; h>=0; h--){
		if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
	}
	return msh[q][0];
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b>>tes;
	for(i=1; i<a; i++){
		cin>>c>>d;
		v[c].push_back(d);
		v[d].push_back(c);
	}
	dfs(1,0);
	for(i=1; i<=b; i++){
		cin>>f[i];
		ss[f[i]].insert(i);
	}
	for(i=1; i<b; i++){
		s[lca(f[i],f[i+1])].insert(i);
	}
	for(t=1; t<=tes; t++){
		cin>>tp;
		if(tp==1){
			cin>>c>>d;
			ss[f[c]].erase(ss[f[c]].lower_bound(c));
			if(c!=1){
				zx=lca(f[c-1],f[c]);
				s[zx].erase(s[zx].lower_bound(c-1));
			}
			if(c!=b){
				zx=lca(f[c],f[c+1]);
				s[zx].erase(s[zx].lower_bound(c));
			}
			f[c]=d;
			ss[f[c]].insert(c);
			if(c!=1){
				zx=lca(f[c-1],f[c]);
				s[zx].insert(c-1);
			}
			if(c!=b){
				zx=lca(f[c],f[c+1]);
				s[zx].insert(c);
			}
		}else{
			cin>>c>>d>>e;
			it=ss[e].lower_bound(c);
			pas1=pas2=-1;
			if(it!=ss[e].end()){
				if((*it)<=d){
					pas1=pas2=(*it);
				}
			}
			it=s[e].lower_bound(c);
			if(it!=s[e].end()){
				if((*it)<d){
					pas1=(*it);
					pas2=(*it)+1;
				}
			}
			cout<<pas1<<" "<<pas2<<endl;
		}
	}
	return 0;
}

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