Submission #636073

#	Time	Username	Problem	Language	Result	Execution time	Memory
636073		pedroslrey	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4053 ms	66124 KiB

treearray

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int MAXK = 19;

vector<int> graph[MAXN];
int dp[MAXN][MAXK];
int as[MAXN], prof[MAXN];
set<int> pos[MAXN], pos_lca[MAXN];

void dfs(int u, int p) {
	for (int v: graph[u]) {
		if (v == p) continue;

		prof[v] = prof[u] + 1;
		dp[v][0] = u;
		for (int k = 1; k < MAXK; ++k)
			dp[v][k] = dp[dp[v][k-1]][k-1];

		dfs(v, u);
	}
}

int lca(int a, int b) {
	if (prof[a] > prof[b]) swap(a, b);

	int d = prof[b] - prof[a];
	for (int k = 0; k < MAXK; ++k)
		if (d & (1 << k)) b = dp[b][k];

	if (a == b) return a;

	for (int k = MAXK - 1; k >= 0; --k)
		if (dp[a][k] != dp[b][k]) {
			a = dp[a][k];
			b = dp[b][k];
		}

	return dp[a][0];
}

int main() {
	int n, m, q;
	cin >> n >> m >> q;

	for (int i = 0; i < n-1; ++i) {
		int u, v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	dfs(1, 1);

	for (int i = 1; i <= m; ++i)
		cin >> as[i];

	for (int i = 1; i <= m; ++i) {
		pos[as[i]].insert(i);
		if (i < m) 
			pos_lca[lca(as[i], as[i+1])].insert(i);
	}

	for (int qq = 0; qq < q; ++qq) {
		int t;
		cin >> t;

		if (t == 1) {
			int i, v;
			cin >> i >> v;

			pos[as[i]].erase(i);
			if (i > 1) pos_lca[lca(as[i-1], as[i])].erase(i-1);
			if (i < m) pos_lca[lca(as[i], as[i+1])].erase(i);

			as[i] = v;

			pos[as[i]].insert(i);
			if (i > 1) pos_lca[lca(as[i-1], as[i])].insert(i-1);
			if (i < m) pos_lca[lca(as[i], as[i+1])].insert(i);
		}
		else {
			int l, r, v;
			cin >> l >> r >> v;
			auto b = lower_bound(pos[v].begin(), pos[v].end(), l);
			auto e = upper_bound(pos[v].begin(), pos[v].end(), r);

			if (b != e) {
				cout << *b << " " << *b << "\n";
				continue;
			}

			auto blca = lower_bound(pos_lca[v].begin(), pos_lca[v].end(), l);
			auto elca = upper_bound(pos_lca[v].begin(), pos_lca[v].end(), r);

			if (blca != elca && *blca + 1 <= r) {
				cout << *blca << " " << *blca + 1 << "\n";
				continue;
			}
			cout << "-1 -1\n";
		}
	}
}

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