Submission #1149803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149803		aktilek	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	5956 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++) {
				if (a[i] == v) {
					ansl =i;
					ansr = i;
				}
			}
			
			if (ansl != -1) {
				cout << ansl << ' ' << ansr << '\n';
				continue;
			}
			
			set < int > st;
			int sz = 0;
			
			for (int i = l; i <= r; i++) {
				if (pref[i] == pref[i - 1]) {
					sz++;
					for (int x : g[v]) {
						if (upper(x, a[i])) {
							st.insert(x);
						}
					}
				}
				
				if (pref[i] == pref[i - 1] + 1 || i == r) {
					if (int(st.size()) != 1) {
						if (i == r) {
							if (pref[i] == pref[i - 1] + 1) {
								ansl = i - sz;
								ansr = i - 1;
							} else {
								ansl = i - sz + 1;
								ansr = i;
							}
						} else {
							ansl = i - sz;
							ansr = i - 1;
						}
					}
					st.clear();
					sz = 0;
				}
			}
			
			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: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44