Submission #382379

#	Time	Username	Problem	Language	Result	Execution time	Memory
382379		ritul_kr_singh	Birthday gift (IZhO18_treearray)	C++17	0 / 100	1 ms	364 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

vector<vector<int>> g;
vector<array<int, 19>> p;
vector<int> t0, t1;
int dfsTimer = 0;

void dfs(int u, int parent){
	t0[u] = dfsTimer++;
	p[u][0] = parent;
	for(int i=1; i<19; ++i) p[u][i] = p[p[u][i-1]][i-1];
	for(int v : g[u]) if(v != parent) dfs(v, u);
	t1[u] = dfsTimer++;
}

bool isAncestor(int u, int v){
	return t0[u]<=t0[v] and t1[v]<=t1[u];
}

int lca(int u, int v){
	if(isAncestor(u, v)) return u;
	if(isAncestor(v, u)) return v;
	for(int i=18; i>=0; --i)
		while(u and !isAncestor(p[u][i], v)) u = p[u][i];
	return p[u][0];
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q, x, y, type; cin >> n >> m >> q;
	g.resize(n), p.resize(n), t0.resize(n), t1.resize(n);
	for(int i=1; i<n; ++i){
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0, 0);
	// for(int i=0; i<n; ++i)
	// 	for(int j=i; j<n; ++j)
	// 		cout << i+1 sp j+1 sp lca(i, j)+1 nl;
	vector<int> a(m), pos(n, -1);
	vector<set<int>> pairs(n);
	for(int i=0; i<m; ++i){
		cin >> a[i]; --a[i];
		pos[a[i]] = i;
		if(i) pairs[lca(a[i], a[i-1])].insert(i-1);
	}

	while(q--){
		cin >> type >> x >> y;
		--x, --y;
		if(type==1){
			if(x+1<m){
				pairs[lca(a[x], a[x+1])].erase(x);
				pairs[lca(y, a[x+1])].insert(x);
			}
			if(x){
				pairs[lca(a[x], a[x-1])].erase(x-1);
				pairs[lca(y, a[x-1])].insert(x-1);
			}
			pos[a[x]] = -1;
			pos[y] = x;
			a[x] = y;
		}else{
			int v; cin >> v; --v;
			if(x<=pos[v] and pos[v]<=y){
				cout << pos[v]+1 sp pos[v]+1 nl;
				continue;
			}
			auto f = pairs[v].lower_bound(x);
			if(f!=pairs[v].end() and *f<y) cout << *f+1 sp *f+2 nl;
			else cout << -1 sp -1 nl;
		}
	}

}

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