답안 #912788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912788 2024-01-19T22:51:46 Z OAleksa Birthday gift (IZhO18_treearray) C++14
0 / 100
9 ms 29276 KB
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 18;
int up[N][K], a[N], tin[N], tout[N], timer, m;
int n, q;
vector<int> g[N];
set<int> st1[N], st2[N];
bool anc(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> m >> q;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= m;i++) {
  		cin >> a[i];
  		st1[a[i]].insert(i);
  	}
  	for (int i = 2;i <= m;i++) {
  		int x = Lca(a[i], a[i - 1]);
  		st2[x].insert(i);
  	}
  	while (q--) {
  		int t;
  		cin >> t;
  		if (t == 1) {
  			int i, v;
  			cin >> i >> v;
  			int lc1 = -1, lc2 = -1;
  			if (i > 0)
  				lc1 = Lca(a[i], a[i - 1]);
  			if (i < m)
  				lc2 = Lca(a[i], a[i + 1]);
  			if (lc1 != -1)
  				st2[lc1].erase(i);
  			if (lc2 != -1)
  				st2[lc2].erase(i + 1);
  			st1[a[i]].erase(i);
  			a[i] = v;
  			st1[a[i]].insert(i);
  		}
  		else {
  			int tl, tr, v;
  			cin >> tl >> tr >> v;
  			int x = -1, y = -1;
  			auto u1 = st1[v].lower_bound(tl);
  			auto u2 = st2[v].lower_bound(tl);
  			if (u1 != st1[v].end()) {
  				if (*u1 <= tr)
  					x = y = *u1;
  			}
  			else if (u2 != st2[v].end()) {
  				if (*u2 <= tr) {
  					y = *u2;
  					x = y - 1;
  				}
  			}
  			cout << x << ' ' << y << '\n';
  		}
  	}
	}
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 29132 KB n=5
2 Incorrect 9 ms 29276 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 29132 KB n=5
2 Incorrect 9 ms 29276 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 29132 KB n=5
2 Incorrect 9 ms 29276 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 29132 KB n=5
2 Incorrect 9 ms 29276 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -