제출 #376508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376508		SeDunion	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4053 ms	57072 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

vector<int>g[N];

const int LOG = 20;

int tin[N], tout[N], up[LOG][N], timer;

void dfs(int v, int p = 1) {
	tin[v] = timer++;
	up[0][v] = p; for (int i = 1 ; i < LOG ; ++ i) up[i][v] = up[i - 1][up[i - 1][v]];
	for (int to : g[v]) if (to != p) {
		dfs(to, v);
	}
	tout[v] = timer++;
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (!upper(up[i][a], b)) a = up[i][a];
	}
	return up[0][a];
}

int a[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1 ; i < n ; ++ i) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1);
	for (int i = 1 ; i <= m ; ++ i) {
		cin >> a[i];
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, v;
			cin >> i >> v;
			a[i] = v;
			continue;
		}
		int l, r, v;
		cin >> l >> r >> v;
		if (a[l] == v) {
			cout << l << " " << l << "\n";
			continue;
		}
		bool ok = 0;
		for (int i = l + 1 ; i <= r ; ++ i) {
			if (a[i] == v) {
				cout << i << " " << i << "\n";
				ok = 1;
				break;
			}
			if (lca(a[i], a[i - 1]) == v) {
				cout << i - 1 << " " << i << "\n";
				ok = 1;
				break;
			}
		}
		if (!ok) cout << "-1 -1\n";
	}
}

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