Submission #942593

#	Time	Username	Problem	Language	Result	Execution time	Memory
942593		gustavo_d	Birthday gift (IZhO18_treearray)	C++17	56 / 100	754 ms	856 KiB

treearray

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

const int MAXN = 2000;
const int MAXLOG = 14;

vector<int> adj[MAXN];
int f[MAXLOG+1][MAXN];
int nivel[MAXN];
bool vis[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);
			}
		}
	}
}

// DP de memorização se der TLE
int LCA(int u, int v) {
	if (u == -1) return v;
	if (v == -1) return u;
	if (nivel[u] < nivel[v]) swap(u, v);
	// sobe o u
	for (int b=MAXLOG; b>=0; b--) {
		if (f[b][u] != -1 and nivel[f[b][u]] >= nivel[v]) {
			u = f[b][u];
		}
	}

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

struct Node {
	int lca;

	Node(int _lca=-1): lca(_lca) {}

	Node operator+(Node right) {
		Node left = *this;
		return LCA(
			left.lca,
			right.lca
		);
	}
};

struct SEG {
	vector<Node> seg;
	int n, actual_lca;
	vector<pair<int, pair<int,int>>> possible;

	SEG(vector<int> &a) {
		n = 1;
		while (n < (int)a.size()) n <<= 1;

		seg = vector<Node> (2 * n);
		for (int i=0; i<(int)a.size(); i++) {
			seg[i+n].lca = a[i];
		}
		for (int i=n-1; i>=0; i--) {
			seg[i] = seg[2*i] + seg[2*i+1];
		}
	}

	void update(int v, int l, int r, int i, int val) {
		if (l == r) {
			seg[v] = val;
			return;
		}

		int m = (l + r) / 2;
		if (i <= m) update(2*v, l, m, i, val);
		else update(2*v+1, m+1, r, i, val);
		seg[v] = seg[2*v] + seg[2*v+1];
	}

	pair<int, pair<int,int>> find_start_node(int l, int r, int v) {
		possible.clear();
		find_nodes(1, 0, n-1, l, r);

		int act = -1;
		for (pair<int, pair<int,int>> node : possible) {
			actual_lca = act;
			act = LCA(act, seg[node.first].lca);
			if (nivel[act] <= nivel[v]) {
				// é um mais alto
				return node;
			}
		}
		return {-1, {-1,-1}};
	}

	void find_nodes(int v, int l, int r, int a, int b) {
		// contido
		if (a <= l and r <= b) {
			possible.push_back({v, {l, r}});
			return;
		}

		// fora
		if (r < a or l > b) return;

		// pacialmente contido
		int m = (l + r) / 2;
		find_nodes(2*v, l, m, a, b);
		find_nodes(2*v+1, m+1, r, a, b);
	}

	int busca_bin(int v, int l, int r, int val) { // primeira posição com lca = v
		if (l == r) {
			if (LCA(actual_lca, seg[v].lca) == val) return l;
			else return -1;
		}

		int m = (l + r) / 2;
		if (nivel[LCA(actual_lca, seg[2*v].lca)] <= nivel[val]) {
			return busca_bin(2*v, l, m, val);
		} else {
			actual_lca = LCA(actual_lca, seg[2*v].lca); // considera range da esquerda já
			return busca_bin(2*v+1, m+1, r, val);
		}
	}
};

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);
	// binary lifting
	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]];
			}
		}
	}

	vector<int> a(m);
	for (int i=0; i<m; i++) {
		cin >> a[i];
		a[i]--;
	}
	SEG seg = SEG(a);

	for (int q=0; q<qs; q++) {
		int type; cin >> type;
		if (type == 1) {
			int pos, v; cin >> pos >> v;
			// update a[pos] = v;
			pos--; v--;
			seg.update(1, 0, seg.n-1, pos, v);
		} else if (type == 2) {
			int l, r, v; cin >> l >> r >> v;
			l--; r--; v--;
			// -1 -1 ou o x, y com LCA do range = v
			pair<int, int> ans = {-1,-1};
			// cout << "query\n";
			for (int start=l; start<=r and ans == make_pair(-1,-1); start++) {
				pair<int, pair<int,int>> start_node = seg.find_start_node(start, r, v);
				if (start_node.first == -1) continue;
				// cout << start << ' ' << start_node.first << endl;

				ans.second = seg.busca_bin(
					start_node.first,
					start_node.second.first,
					start_node.second.second,
					v
				);
				// cout << ans.second << endl;
				if (ans.second != -1) {
					ans.first = start;
				}
			}
			if (ans == make_pair(-1,-1)) ans = {-2, -2};
			cout << ans.first+1 << ' ' << ans.second+1 << '\n';
		}
	}

	return 0;
}

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