Submission #1134740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134740		Agageldi	Birthday gift (IZhO18_treearray)	C++17	0 / 100	5 ms	9796 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 400005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()

ll n, t, a[N], q, m, lvl[N], vis[N], sp[N][30], par[N], cnt;
vector <int> v[N];
void solve(int x) {
	vis[x] = cnt;
	for(auto i:v[x]) {
		if(vis[i] > 0) continue;
		if(x == 1) cnt++;
		solve(i);
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++) {
		int pos, x, l, r;
		cin >> t;
		bool tr = 0;
		if(t == 1) {
			cin >> pos >> x;
			a[pos] = x;
			continue;
		}
		cin >> l >> r >> x;
		for(int j = 1; j <= n; j++) {
			vis[j] = -1;
		}
		for(int j=l;j<=r;j++) {
			if(a[j] == x) {
				tr = 1;
				cout << j << " " << j << '\n';
				break;
			}
		}
		cnt = 1;
		solve(x);
		for(int j = l; j < r; j++) {
			if(~vis[a[j]] && ~vis[a[j + 1]] && !tr && vis[a[j]] != vis[a[j + 1]]) {
				cout << j << " " << j + 1 << '\n';
				tr = 1;
				break;
			}
		}
		if(!tr) cout << "-1 -1" << '\n';
	}
}

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