Submission #865193

#	Time	Username	Problem	Language	Result	Execution time	Memory
865193		vjudge1	Birthday gift (IZhO18_treearray)	C++17	0 / 100	4 ms	10844 KiB

treearray

#include <bits/stdc++.h>
 
#define optimus_prime ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) (a.begin() , a.end())
#define ll int
#define pb push_back
#define sz() size()
 
using namespace std;
 
const ll N = 2e5+9;
const ll L = 30;

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

void calc(ll cur , ll p , ll len=1){
	h[cur]=len;
	tin[cur]=++timer;
	up[cur][0]=p;
	for (int i = 1 ; i <= L ; i++){
		up[cur][i]=up[up[cur][i-1]][i-1];
	}
	for (auto to : g[cur]){
		if (to!=p){
			calc(to , cur , len+1);
		}
	}
	tout[cur]=timer;
}

bool upper(ll a , ll b){
	if (tin[a]<=tin[b]&&tout[b]<=tout[a])return 1;
	return 0;
}

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

void solve(){
	cin >> n >> m >> q;
	for (int i = 1 ; i < n ; i++){
		ll u , v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	for (int i = 1 ; i <= m ; i++)cin >> a[i];
	calc(1 , 1);
	while (q--){
		ll tp;
		cin >> tp;
		if (tp==1){
			ll pos , v;
			cin >> pos >> v;
			a[pos]=v;
		}
		else {
			ll l , r , v , ok=0;
			cin >> l >> r >> v;
			for (int i = l ; i <= r ; i++){
				if (a[i]==v){
					cout << i << " " << i << "\n";
					ok=1;
					break;
				}
			}
			if (ok)continue;
			while (h[a[l]]<=h[v])l++;
			while (h[a[r]]<=h[v])r--;
			for (int x = l ; x <= r ; x++){
				if (ok)break;
				for (int y = x ; y <= r ; y++){
					ll niga=a[x];
					for (int i = x ; i <= y ; i++){
						niga=lca(a[i] , niga);
						if (h[niga]<h[v])break;
					}
					if (niga==v){
						cout << x << " " << y << "\n";
						ok=1;
						break;
					}
				}
				if (ok)break;
			}
			if (!ok)cout << "-1 -1\n";
		}
	}
}
	
signed main() {
	optimus_prime;
	solve();
return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'void calc(int, int, int)':
treearray.cpp:22:13: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
   22 |   up[cur][i]=up[up[cur][i-1]][i-1];
      |   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:21:21: note: within this loop
   21 |  for (int i = 1 ; i <= L ; i++){
      |                   ~~^~~~

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