Submission #336217

#	Time	Username	Problem	Language	Result	Execution time	Memory
336217		super_j6	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4062 ms	35024 KiB

treearray

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200000, k = __lg(mxn - 1) + 1;
int n, m, q;
int a[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];

void dfs(int c){
	for(int i = 1; i < k; i++) p[i][c] = ~p[i][c] ? p[i - 1][p[i - 1][c]] : -1;
	for(int i : g[c]) if(i != p[0][c]) d[i] = d[c] + 1, p[0][i] = c, dfs(i);
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = k - 1; ~i; i--) if(~p[i][x] && d[p[i][x]] >= d[y]) x = p[i][x];
	for(int i = k - 1; ~i; i--) if(p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
	return x == y ? x : p[0][x];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	p[0][0] = -1;
	dfs(0);
	
	for(int i = 0; i < m; i++) cin >> a[i], a[i]--;
	
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			a[--x] = --y; 
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			l--, r--, x--;
			pi p = {-2, -2};
			for(int i = l; i <= r; i++){
				if(a[i] == x){
					p = {i, i};
					break;
				}else if(i < r && lca(a[i], a[i + 1]) == x){
					p = {i, i + 1};
					break;
				}
			}
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

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