Submission #339675

#	Time	Username	Problem	Language	Result	Execution time	Memory
339675		wind_reaper	Birthday gift (IZhO18_treearray)	C++17	0 / 100	1 ms	384 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

struct LCA{
	vector<int> tin, tout; 
	vector<vector<int>> adj; 
	vector<vector<int>> up; 
	int N, l; 
	int timer = 0; 
	void init(int n){
		l = ceil(log2(n));
		up.resize(n, vector<int>(l+1));
		tin.resize(n); 
		adj.resize(n); 
		tout.resize(n); 
		N = n;  
	}

	void dfs(int node, int p){
		tin[node] = timer++; 

		up[node][0] = p; 

		for(int j = 1; j <= l; j++){
			up[node][j] = up[up[node][j-1]][j-1]; 
		}

		for(int v : adj[node]){
			if(v == p) 
				continue; 
			dfs(v, node); 
		}

		tout[node] = timer++; 
	}

	bool is_ancestor(int u, int v){
		return tin[u] <= tin[v] && tout[u] >= tout[v]; 
	}

	int lca(int u, int v){
		if(is_ancestor(u, v)) 
			return u; 
		if(is_ancestor(v, u))
			return v; 

		for(int i = l; i >= 0; --i){
			if(!is_ancestor(up[u][i], v))
				u = up[u][i]; 
		}

		return up[u][0]; 
	}
}; 
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

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

	L.dfs(0, 0);

	vector<multiset<int>> lcas(n); 	
	vector<int> arr(m); 
	for(int i = 0; i < m; i++){
		cin >> arr[i]; 
		--arr[i];
		lcas[arr[i]].insert(i); 
	}

	for(int i = 0; i < m - 1; i++)
		lcas[L.lca(arr[i], arr[i+1])].insert(i); 

	for(int x = 0; x < q; x++){
		int t;
		cin >> t; 
		if(t == 1){
			int i, v;
			cin >> i >> v; 
			--i, --v; 
			int r = L.lca(arr[i], arr[i+1]); 
			if(i < m - 1) lcas[r].erase(lcas[r].find(i));
			r = L.lca(arr[i], arr[i-1]);
			if(i > 0) lcas[r].erase(lcas[r].find(i-1)); 	
			lcas[arr[i]].erase(lcas[arr[i]].find(i)); 

			arr[i] = v; 
			if(i < m - 1) lcas[L.lca(arr[i+1], arr[i])].insert(i); 
			if(i > 0) lcas[L.lca(arr[i], arr[i-1])].insert(i-1); 
			lcas[arr[i]].insert(i); 
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			--l, --r, --v;
			auto it = lcas[v].lower_bound(l); 

			int x = -2, y = -2; 

			if(it != lcas[v].end() && *it <= r){
				if(arr[*it] == v)
					x = *it, y = *it; 
				else x = *it, y = *it + 1; 
			}

			cout << x+1 << ' ' << y+1 << '\n';
		}
	}
	return 0; 
}

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