Submission #1283991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283991		WH8	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1109 ms	96724 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double

signed main(){
	//~ cin.tie(0);
	//~ ios::sync_with_stdio(0);
	int n,m,q;cin>>n>>m>>q;
	vector<vector<int>> al(n+1);
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		al[a].pb(b);
		al[b].pb(a);
	}
	vector<vector<int>> up(n+1, vector<int>(20, 0));
	vector<int> dep(n+1, 0);
	auto dfs=[&](auto && dfs, int x, int p)->void{
		for(auto it:al[x]){
			if(it!=p){
				dep[it]=dep[x]+1;
				up[it][0]=x;
				dfs(dfs, it, x);
			}
		}
	};
	dfs(dfs, 1, 0);
	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			up[i][j]=up[up[i][j-1]][j-1];
		}
	}
	auto lca=[&](int a, int b)->int{
		
		//~ printf("lca of %lld %lld\n", a,b);
		if(dep[a] < dep[b])swap(a,b);
		int raiseby=dep[a]-dep[b];
		for(int i=0;i<20;i++) if((1<<i)&raiseby)a=up[a][i];
		if(a==b)return a;

		for(int i=19;i>=0;i--) if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
		//~ printf("is %lld\n", up[a][0]);
		return up[a][0];
	};
	vector<set<pair<int,int>>> pos(n+1);
	vector<int> v(m+1);
	for(int i=1;i<=m;i++){
		cin>>v[i];
		pos[v[i]].insert({i, i});
	}
	for(int i=1;i<m;i++){
		pos[lca(v[i], v[i+1])].insert({i, i+1});
	}
	for(int qind=0;qind<q;qind++){
		int t,a,b,c;cin>>t>>a>>b;
		if(t==1){
			if(a!=1){
				c=lca(v[a], v[a-1]);
				pos[c].erase({a-1, a});
			}
			if(a!=m){
				c=lca(v[a], v[a+1]);
				pos[c].erase({a, a+1});
			}
			pos[v[a]].erase({a, a});
			v[a]=b;
			
			if(a!=1){
				c=lca(v[a], v[a-1]);
				pos[c].insert({a-1, a});
			}
			if(a!=m){
				c=lca(v[a], v[a+1]);
				pos[c].insert({a, a+1});
			}			
			pos[v[a]].insert({a, a});
		}
		if(t==2){
			cin>>c;
			auto it=pos[c].lower_bound({a, a});
			if(it!=pos[c].end() and (*it).s <= b){
				cout<<(*it).f<<" "<<(*it).s<<'\n';
			}
			else {
				cout<<"-1 -1\n";
			}
		}
		//~ for(int i=1;i<=n;i++){
			//~ printf("%lld: ",i);
			//~ for(auto [l, r]:pos[i]){
				//~ printf("(%lld %lld) ",l,r);
			//~ }
			//~ cout<<endl;
		//~ }
	}
		 
}

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