Submission #1149794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149794		aktilek	Birthday gift (IZhO18_treearray)	C++20	30 / 100	4094 ms	6212 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 2e5 + 7;
const int R = 1e9 + 10;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int B = 320;

vector < int > g[N];
int a[N], tin[N], tout[N], timer, up[N][22], d[N];

void dfs(int v, int p) {
	if (p == 0) up[v][0] = v;
	else up[v][0] = p;
	tin[v] = timer++;
	
	if (p == 0) {
		d[v] = 0;
	} else {
		d[v] = d[p] + 1;
	}
	
	for (int i = 1; i <= 20; i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	
	for (int to : g[v]) {
		if (to == p) continue;
		dfs(to, v);
	}
	tout[v] = timer++;
}

bool upper(int x, int y) {
	if (tin[x] <= tin[y] && tout[y] <= tout[x]) {
		return true;
	}
	return false;
}

int lca(int x, int y) {
	if (upper(x, y)) return x;
	if (upper(y, x)) return y;
	
	for (int i = 20; i >= 0; i--) {
		if (!upper(up[x][i], y)) {
			x = up[x][i];
		}
	}
	return up[x][0];
}

void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	dfs(1, 0);
	
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
	}
	
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int pos, v;
			cin >> pos >> v;
			a[pos] = v;
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			
			int pref[N];
			pref[l - 1] = 0;
			for (int i = l; i <= r; i++) {
				if (upper(v, a[i]) == false) {
					pref[i] = pref[i - 1] + 1;
				} else {
					pref[i] = pref[i - 1];
				}
				// cout << pref[i] << ' ';
			}
			// cout << '\n';
			
			int ansl = -1, ansr = -1;
			
			for (int i = l; i <= r; i++) {
				for (int j = i; j <= r; j++) {
					if (lca(a[i], a[j]) == v && pref[j] - pref[i - 1] == 0) {
						ansl = i;
						ansr = j;
					}
				}
			}
			
			cout << ansl << ' ' << ansr << '\n';
		}
	}
	
}

int main() {
  	// freopen("gates.in", "r", stdin);
  	// freopen("gates.out", "w", stdout);
  	Fast
  
  	int tc = 1;
  	// cin >> tc;
  
  	while (tc--) {
    	solve();
  	}
}

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