Submission #1134748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134748		Agageldi	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4078 ms	21756 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, vis[N], par[N], cnt;
vector <int> v[N];

void solve(int x) {
	vis[x] = cnt;
	for(auto i : v[x]) {
		if(i == par[x]) continue;
		if(vis[x] == 1) cnt++;
		solve(i);
	}
}
void find(int x) {
	vis[x] = 1;
	for(auto i : v[x]) {
		if(vis[i]) continue;
		par[i] = x;
		find(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);
	}
	find(1);
	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] = 0;
		}
		for(int j=l;j<=r;j++) {
			if(a[j] == x) {
				tr = 1;
				cout << j << " " << j << '\n';
				break;
			}
		}
		if(tr) continue;
		cnt = 1;
		solve(x);
		for(int j = l; j < r; j++) {
			if(min(vis[a[j]],vis[a[j+1]]) > 0 && vis[a[j]] != vis[a[j+1]]) {
				tr = 1;
				cout << j << " " << j + 1 << '\n';
				break;
			}
		}
		if(!tr) cout << "-1 -1" << '\n';
	}
}
/*
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
*/
/*
5 4 1
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 3
*/

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