제출 #1283681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283681		Jawad_Akbar_JJ	Birthday gift (IZhO18_treearray)	C++20	0 / 100	13 ms	24984 KiB

treearray

#include <iostream>
#include <vector>
#include <set>

using namespace std;
const int N = 1<<18;
vector<int> nei[N];
set<int> Vc[N], occ[N];
int par[N][18], hei[N], ps[N];

void dfs(int u, int p){
	par[u][0] = p, hei[u] = hei[p] + 1;
	for (int i=1;i<18;i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for (int i : nei[u])
		if (i != p)
			dfs(i, u);
}

int Lca(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);
	for (int i=17;i>=0;i--){
		if ((1<<i) + hei[u] <= hei[v])
			v = par[v][i];
	}
	for (int i=17;i>=0;i--){
		if (par[u][i] != par[v][i])
			u = par[u][i], v = par[v][i];
	}
	return (u == v ? u : par[u][0]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, q;
	cin>>n>>m>>q;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	dfs(1, 0);

	for (int i=1;i<=m;i++){
		cin>>ps[i];
		if (i > 1)
			Vc[Lca(ps[i], ps[i-1])].insert(i);
		occ[ps[i]].insert(i);
	}

	for (int i=1, t, l, r, pos, v;i<=q;i++){
		cin>>t;
		if (t == 1){
			cin>>pos>>v;
			occ[ps[pos]].erase(pos);
			if (pos > 1){
				Vc[Lca(ps[pos], ps[pos-1])].erase(pos);
				Vc[Lca(v, ps[pos-1])].insert(pos);
			}
			if (pos < m){
				Vc[Lca(ps[pos], ps[pos+1])].erase(pos);
				Vc[Lca(v, ps[pos+1])].insert(pos);
			}
			ps[pos] = v;
			occ[v].insert(pos);
			continue;
		}

		cin>>l>>r>>v;
		auto u = Vc[v].upper_bound(l);
		auto U = occ[v].upper_bound(l - 1);

		if (U != occ[v].end() and *U <= r)
			cout<<(*U)<<" "<<(*U)<<'\n';
		else if (u != Vc[v].end() and *u <= r)
			cout<<(*u) -1<<" "<<(*u)<<'\n';
		else
			cout<<"-1 -1\n";
	}
}

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