Submission #171666

#	Time	Username	Problem	Language	Result	Execution time	Memory
171666		Lightning	Birthday gift (IZhO18_treearray)	C++14	56 / 100	4026 ms	34156 KiB

treearray

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int LG = 18;

int n, m, q, a[N];
vector <int> g[N];
int up[N][20], tin[N], tout[N], timer;

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

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

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

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) {
		int p, q;
		cin >> p >> q;
		g[p].pb(q);
		g[q].pb(p);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; ++i) {
		cin >> a[i];
	}
	for(int it = 1; it <= q; ++it) {
		int type;
		cin >> type;
		if(type == 1) {
			int pos, v;
			cin >> pos >> v;
			a[pos] = v;
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			pii ans = {-1, -1};	 
			for(int i = l; i <= r; ++i) {
				int res = a[i];
				int cur = i;
				while(i <= r && is_ancestor(v, a[i])) {
					res = lca(res, a[i]);
					++i;
				}
				if(res == v) {
					ans = {cur, i - 1};
				}
			}	
			cout << ans.F <<' '<< ans.S <<'\n';
		} 
	}
	return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5 
2 1 3 1
*/

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