Submission #937355

#	Time	Username	Problem	Language	Result	Execution time	Memory
937355		gustavo_d	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1925 ms	58244 KiB

treearray

// https://oj.uz/problem/view/IZhO18_treearray > p203
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;
const int MAXLOG = 20;

vector<int> adj[MAXN];
int a[MAXN];

int nivel[MAXN];
bool vis[MAXN];
int f[MAXLOG+1][MAXN];

void BFS(int src) {
	vis[src] = true;
	nivel[src] = 0;
	f[0][src] = -1;
	queue<int> visit; visit.push(src);
	while (!visit.empty()) {
		int v = visit.front();
		visit.pop();
		for (int viz : adj[v]) {
			if (!vis[viz]) {
				vis[viz] = true;
				nivel[viz] = nivel[v] + 1;
				f[0][viz] = v;
				visit.push(viz);
			}
		}
	}
}

int LCA(int x, int y) {
	if (nivel[x] < nivel[y]) swap(x, y); // x sobe
	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][x] != -1 and nivel[f[b][x]] >= nivel[y]) {
			x = f[b][x];
		}
	}
	if (x == y) return x;

	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][x] != -1 and f[b][y] != -1 and f[b][x] != f[b][y]) {
			x = f[b][x];
			y = f[b][y];
		}
	}

	return f[0][x];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n, m, qs; cin >> n >> m >> qs;
	for (int i=0; i<n-1; i++) {
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	// LCA
	BFS(0);
	for (int b=1; b<=MAXLOG; b++) {
		for (int i=0; i<n; i++) {
			if (f[b-1][i] == -1) {
				f[b][i] = -1;
			} else {
				f[b][i] = f[b-1][f[b-1][i]];
			}
		}
	}

	set<pair<int,int>> lcas; // {lca(i, i+1), i}
	set<pair<int,int>> itself;
	for (int i=0; i<m; i++) {
		cin >> a[i];
		a[i]--;
		if (i >= 1) {
			lcas.insert({LCA(a[i-1], a[i]), i-1});
		}
		itself.insert({a[i], i});
	}

	for (int q=0; q<qs; q++) {
		int type; cin >> type;
		if (type == 1) {
			int i, v; cin >> i >> v; // a[i] = v
			i--; v--;

			if (i != m-1) lcas.erase({LCA(a[i], a[i+1]), i});
			if (i != 0) lcas.erase({LCA(a[i-1], a[i]), i-1});
			itself.erase({a[i], i});
			a[i] = v;
			itself.insert({a[i], i});
			if (i != m-1) lcas.insert({LCA(a[i], a[i+1]), i});
			if (i != 0) lcas.insert({LCA(a[i-1], a[i]), i-1});
		} else {
			int l, r, v; cin >> l >> r >> v; // LCA = v entre l e r
			l--; r--; v--;
			auto it = itself.lower_bound({v, l});
			if (it == itself.end() or ((it->first) != v) or ((it->second) > r)) {}
			else {
				cout << (it->second)+1 << ' ' << (it->second) + 1 << '\n';
				continue;
			}
			it = lcas.lower_bound({v, l});
			if (it == lcas.end()) {
				cout << "-1 -1\n";
			} else {
				if ((it->first) != v) cout << "-1 -1\n";
				else if ((it->second) >= r) cout << "-1 -1\n"; // pega r+1 ou maior
				else cout << (it->second)+1 << ' ' << (it->second) + 2 << '\n';
			}
		}
	}

	return 0;
}

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