Submission #385514

#	Time	Username	Problem	Language	Result	Execution time	Memory
385514		vanic	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1759 ms	63852 KiB

treearray

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const int maxn=2e5+5, Log=18;

int n, m, q;
vector < int > ms[maxn];
int parent[maxn][Log];
int dep[maxn];

void dfs(int x, int prosl, int d){
	parent[x][0]=prosl;
	dep[x]=d;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			dfs(ms[x][i], x, d+1);
		}
	}
}

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=0; j<n; j++){
			parent[j][i]=parent[parent[j][i-1]][i-1];
		}
	}
}

void digni(int &a, int &b){
	int raz=dep[a]-dep[b];
	for(int i=0; i<Log; i++){
		if((1<<i)&raz){
			a=parent[a][i];
		}
	}
}

int lca(int a, int b){
	if(dep[a]<dep[b]){
		swap(a, b);
	}
	digni(a, b);
	if(a==b){
		return a;
	}
	for(int i=Log-1; i>-1; i--){
		if(parent[a][i]!=parent[b][i]){
			a=parent[a][i];
			b=parent[b][i];
		}
	}
	return parent[a][0];
}

int l[maxn];
set < pair < int, int > > s;
set < pair < int, int > > s1;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	int a, b;
	for(int i=0; i<n-1; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	dfs(0, 0, 0);
	precompute();
	for(int i=0; i<m; i++){
		cin >> l[i];
		l[i]--;
		s1.insert({l[i], i});
		if(i){
			s.insert({lca(l[i-1], l[i]), i-1});
		}
	}
	int c, d;
	set < pair < int, int > >::iterator it;
	for(int i=0; i<q; i++){
		cin >> a;
		if(a==1){
			cin >> b >> c;
			b--;
			c--;
			s1.erase({l[b], b});
			s1.insert({c, b});
			if(b){
				s.erase({lca(l[b-1], l[b]), b-1});
				s.insert({lca(l[b-1], c), b-1});
			}
			if(b!=m-1){
				s.erase({lca(l[b], l[b+1]), b});
				s.insert({lca(c, l[b+1]), b});
			}
			l[b]=c;
		}
		else{
			cin >> b >> c >> d;
			d--;
			b--;
			c--;
			it=s.lower_bound({d, b});
			if(it!=s.end() && it->first==d && it->second<c){
				cout << it->second+1 << ' ' << it->second+2 << '\n';
			}
			else{
				it=s1.lower_bound({d, b});
				if(it!=s1.end() && it->first==d && it->second<=c){
					cout << it->second+1 << ' ' <<  it->second+1 << '\n';
				}
				else{
					cout << -1 << ' ' << -1 << '\n';
				}
			}
		}
		
	}
	return 0;
}

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