제출 #525429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525429		s_samchenko	Birthday gift (IZhO18_treearray)	C++17	30 / 100	4069 ms	1072 KiB

treearray

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") //bad
//#pragma GCC target("avx,avx2")
#define ll long long
#define ull unsigned ll
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
constexpr ll mod = 1e9+7;
const int N = 3e5+100, B = 430;

vector < vector <int> > g, up;
vector <int> d;

void dfs(int v = 1, int pr = 1, int h = 0){
	d[v] = h;
	up[v][0] = pr;
	for (int j = 1; j <= 19; ++j) up[v][j] = up[up[v][j-1]][j-1];
	for (auto to : g[v]){
		if (to == pr) continue;
		dfs(to, v, h+1);
	}
}

int lca(int u, int v){
	if (d[v] < d[u]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int v1 = up[v][j], u1 = up[u][j];
		if (u1 != v1) u = u1, v = v1;
	}
	return up[v][0];
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	g.resize(n+1);
	up.resize(n+1, vector <int> (20));
	d.resize(n+1);

	for (int i = 1; i < n; ++i){
		int a, b; cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs();
	vector <int> a(m+1);
	for (int i = 1; i <= m; ++i) cin >> a[i];
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, v; cin >> pos >> v;
			a[pos] = v;
			continue;
		}
		int l, r, v; cin >> l >> r >> v;
		int x = -1, y = -1;
		for (int i = l; i <= r; ++i){
			if (lca(a[i], v) != v) continue;
			if (a[i] == v) x = i, y = i;
			int w = a[i];
			for (int j = i + 1; j <= r; ++j){
				if (lca(a[j], v) != v) break;
				w = lca(w, a[j]);
				if (w == v){
					x = i, y = j;
					break;
				}
			}
		}
		cout << x << " " << y << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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