Submission #339782

#	Time	Username	Problem	Language	Result	Execution time	Memory
339782		wind_reaper	Birthday gift (IZhO18_treearray)	C++17	Compilation error	0 ms	0 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 i = 1; i <= l; i++)
			up[node][i] = up[up[node][i-1]][i-1];

		for(int v : adj[node])
			if(v != p)
				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_anc(u, v))
			return u;
		if(is_anc(v, u))
			return v;

		for(int i = l; i >= 0; --i)
			if(!is_anc(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; 

			// for(int k : lcas[v])
			// 	cout << k << ' ';
			// cout << '\n';
			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; 
}

Compilation message (stderr)

treearray.cpp: In member function 'int LCA::lca(int, int)':
treearray.cpp:40:6: error: 'is_anc' was not declared in this scope; did you mean 'isnanl'?
   40 |   if(is_anc(u, v))
      |      ^~~~~~
      |      isnanl
treearray.cpp:42:6: error: 'is_anc' was not declared in this scope; did you mean 'isnanl'?
   42 |   if(is_anc(v, u))
      |      ^~~~~~
      |      isnanl
treearray.cpp:46:8: error: 'is_anc' was not declared in this scope; did you mean 'isnanl'?
   46 |    if(!is_anc(up[u][i], v))
      |        ^~~~~~
      |        isnanl