Submission #1134573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134573		Agageldi	Birthday gift (IZhO18_treearray)	C++17	0 / 100	6 ms	9796 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()

ll n, t, T, a[N], q, m, lvl[N], vis[N], sp[N][30], par[N];
vector <int> v[N], h;
int kth_ancestor(int x,int y) {
	for(int i = 20; i >= 0; i--) {
		if((y & (1 << i))) x = sp[x][i];
	}
	return x;
}
int find(int x,int y) {
	if(lvl[x] > lvl[y]) {
		x = kth_ancestor(x,lvl[x] - lvl[y]);
	}
	if(lvl[x] < lvl[y]) {
		y = kth_ancestor(y,lvl[y] - lvl[x]);
	}
	if(x == y) return x;
	int o = 0;
	for(int i = 20; i >= 0; i--) {
		if(sp[x][i] != sp[y][i]) {
			x = sp[x][i];
			y = sp[y][i];
		}
	}
	return sp[x][0];
}


void solve(int x,int lev) {
	lvl[x] = lev;
	vis[x] = 1;
	for(auto i:v[x]) {
		if(vis[i]) continue;
		sp[i][0] = x;
		solve(i,lev + 1);
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	solve(1,1);
	for(int i = 1;i <= m; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= 20; i++) {
		for(int j = 1; j <= n; j++) {
			sp[j][i] = sp[sp[j][i - 1]][i - 1];
		}
	}
	for(int i = 1; i <= q; i++) {
		int pos, x, l, r;
		cin >> t;
		if(t == 1) {
			cin >> pos >> x;
			a[pos] = x;
			continue; 
		}
		cin >> l >> r >> x;
		bool tr = 0;
		for(int j = l; j <= r; j++) {
			int c = a[j];
			for(int k = j; k >= 1; k--) {
				c = find(c,a[k]);
				if(c == x) {
					tr = 1;
					cout << k << " " << j << '\n';
					break;
				}
			}
			if(tr) break;
		}
		if(!tr) cout <<"-1 -1\n";
	}
}

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