Submission #651305

#	Time	Username	Problem	Language	Result	Execution time	Memory
651305		alvingogo	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1883 ms	69128 KiB

treearray

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct no{
	vector<int> ch;
	int as[20]={0};
	int dep=-1;
};
vector<no> v;
void dfs(int r,int f){
	v[r].as[0]=f;
	v[r].dep=v[f].dep+1;
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
		}
	}
}
int lca(int x,int y){
	if(v[x].dep<v[y].dep){
		swap(x,y);
	}
	for(int i=19;i>=0;i--){
		if(v[v[x].as[i]].dep>=v[y].dep){
			x=v[x].as[i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=19;i>=0;i--){
		if(v[x].as[i]!=v[y].as[i]){
			x=v[x].as[i];
			y=v[y].as[i];
		}
	}
	return v[x].as[0];
}
int main(){
    AquA;
	int n,m,q;
	cin >> n >> m >> q;
	v.resize(n);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		v[a].ch.push_back(b);
		v[b].ch.push_back(a);
	}
	dfs(0,0);
	for(int i=1;i<20;i++){
		for(int j=0;j<n;j++){
			v[j].as[i]=v[v[j].as[i-1]].as[i-1];
		}
	}
	vector<int> g(m);
	multiset<pair<int,pair<int,int> > > s;
	for(int i=0;i<m;i++){
		cin >> g[i];
		g[i]--;
		s.insert({g[i],{i,i}});
	}
	vector<int> y(m);
	for(int i=1;i<m;i++){
		y[i]=lca(g[i-1],g[i]);
		s.insert({y[i],{i-1,i}});
	}
	for(int i=0;i<q;i++){
		int t;
		cin >> t;
		if(t==1){
			int p,k;
			cin >> p >> k;
			k--;
			p--;
			s.erase({g[p],{p,p}});
			if(p){
				s.erase({y[p],{p-1,p}});
			}
			if(p+1<m){
				s.erase({y[p+1],{p,p+1}});
			}
			g[p]=k;
			s.insert({g[p],{p,p}});
			if(p){
				y[p]=lca(g[p],g[p-1]);
				s.insert({y[p],{p-1,p}});
			}
			if(p+1<m){
				y[p+1]=lca(g[p],g[p+1]);
				s.insert({y[p+1],{p,p+1}});
			}
		}
		else{
			int l,r,k;
			cin >> l >> r >> k;
			k--;
			l--;
			r--;
			auto h=s.lower_bound({k,{l,-1}});
			if(h==s.end() || (*h).sc.sc>r || (*h).fs!=k){
				cout << "-1 -1\n";
			}
			else{
				cout << (*h).sc.fs+1 << " " << (*h).sc.sc+1 << "\n";
			}
		}
	}
    return 0;
}

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