Submission #379402

#	Time	Username	Problem	Language	Result	Execution time	Memory
379402		rk42745417	Birthday gift (IZhO18_treearray)	C++17	0 / 100	20 ms	24044 KiB

treearray

/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 2e5 + 25, LGN = 19;
vector<int> edge[N];
int anc[LGN][N], dep[N];

void dfs(int u, int p) {
	for(int v : edge[u])
		if(v != p)
			dep[v] = dep[u] + 1, anc[0][v] = u, dfs(v, u);
}
int lca(int a, int b) {
	if(dep[a] < dep[b])
		swap(a, b);
	for(int i = 0, x = dep[a] - dep[b]; i < LGN; i++)
		if(x >> i & 1)
			a = anc[i][a];
	if(a == b)
		return a;
	for(int i = LGN - 1; ~i; i--) {
		if(anc[i][a] != anc[i][b]) {
			a = anc[i][a];
			b = anc[i][b];
		}
	}
	return anc[0][a];
}

set<int> one[N], two[N];

signed main() { EmiliaMyWife
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs(1, 1);
	vector<int> arr(m + 1);
	for(int i = 1; i <= m; i++)
		cin >> arr[i], one[arr[i]].insert(i);
	for(int i = 2; i <= n; i++)
		two[lca(arr[i - 1], arr[i])].insert(i - 1);
	while(q--) {
		int t;
		cin >> t;
		if(t == 1) {
			int p, v;
			cin >> p >> v;
			one[arr[p]].erase(p);
			if(p > 1)
				two[lca(arr[p - 1], arr[p])].erase(p - 1);
			if(p + 1 <= m)
				two[lca(arr[p], arr[p])].erase(p);
			arr[p] = v;
			one[arr[p]].insert(p);
			if(p > 1)
				two[lca(arr[p - 1], arr[p])].insert(p - 1);
			if(p + 1 <= m)
				two[lca(arr[p], arr[p])].insert(p);
		}
		else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it = one[v].lower_bound(l);
			auto it2 = two[v].lower_bound(l);
			if(it != one[v].end() && *it <= r)
				cout << *it << ' ' << *it << '\n';
			else if(it2 != two[v].end() && *it2 < r)
				cout << *it2 << ' ' << *it2 + 1 << '\n';
			else
				cout << "-1 -1\n";
		}
	}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

*/

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