Submission #543231

#	Time	Username	Problem	Language	Result	Execution time	Memory
543231		MarcosPauloEvers	Birthday gift (IZhO18_treearray)	C++17	100 / 100	935 ms	68624 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10, MAXK = 18;
int n, m;
set<int> pos[MAXN], pos_lca[MAXN];

vector<int> adj[MAXN];
int lift[MAXN][MAXK], depth[MAXN];
int arr[MAXN], arr_lca[MAXN];

void init_lca()
{
	memset(lift, -1, sizeof lift);
	queue<int> que;
	que.push(1);
	lift[1][0] = 1;
	depth[1] = 0;
	while(!que.empty())
	{
		int v = que.front(); que.pop();

		for(int u: adj[v])
			if(lift[u][0] == -1)
				lift[u][0] = v, depth[u] = depth[v] + 1, que.push(u);
	}

	for(int k = 1; k < MAXK; k++)
		for(int i = 1; i <= n; i++)
			lift[i][k] = lift[lift[i][k-1]][k-1];
}

int get_lca(int u, int v)
{
	if(depth[u] < depth[v]) swap(u, v);

	for(int k = MAXK - 1; k >= 0; k--)
		if(depth[u] - (1 << k) >= depth[v])
			u = lift[u][k];

	if(u == v) return u;

	for(int k = MAXK - 1; k >= 0; k--)
		if(lift[u][k] != lift[v][k])
			u = lift[u][k], v = lift[v][k];

	return lift[u][0];
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int q;
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;

		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	init_lca();
	for(int i = 1; i <= m; i++)
	{
		cin >> arr[i];

		pos[arr[i]].insert(i);
	}
	
	for(int i = 1; i < m; i++)
		pos_lca[get_lca(arr[i], arr[i+1])].insert(i);

	while(q--)
	{
		int op; cin >> op;

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

			if(i > 1)
			{
				pos_lca[get_lca(arr[i - 1], arr[i])].erase(i - 1);
				pos_lca[get_lca(arr[i - 1], v)].insert(i - 1);
			}

			if(i < m)
			{
				pos_lca[get_lca(arr[i], arr[i + 1])].erase(i);
				pos_lca[get_lca(v, arr[i + 1])].insert(i);
			}

			pos[arr[i]].erase(i);
			pos[v].insert(i);

			arr[i] = v;
		} else
		{
			int l, r, v; cin >> l >> r >> v;

			auto it1 = pos[v].lower_bound(l);
			auto it2 = pos_lca[v].lower_bound(l);

			if(it1 != pos[v].end() && *it1 <= r)
				cout << *it1 << " " << *it1 << "\n";
			else if(it2 != pos_lca[v].end() && *it2 < r)
				cout << *it2 << " " << *it2 + 1 << "\n";
			else
				cout << -1 << " " << -1 << "\n";
		}
	}
	return 0;
}

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