oj.uz

Submission #505008

# Submission time Handle Problem Language Result Execution time Memory
505008 2022-01-10T11:39:49 Z Mazaalai Birthday gift (IZhO18_treearray) C++17
0 / 100
 14 ms 24596 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const int M = 20;
int n, m, q;
int nums[N], vals[N], lvl[N];
int jump[N][M];
set <int> positions[N], positions1[N];
vector <int> paths[N];
int jumpUp(int pos, int len) {
	for (int i = 0; (1<<i)<=len; i++) 
		if (len & (1<<i)) 
			pos = jump[pos][i];
	
	return pos;
}
int LCA(int a, int b) {
	if (lvl[a] > lvl[b]) swap(a, b);
	int dif = lvl[b] - lvl[a];
	b = jumpUp(b, dif);
	for (int i = M-1; i >= 0 && a != b; i--) {
		if (jump[a][i] != jump[b][i]) {
			a = jump[a][i];
			b = jump[b][i];
		}
	}
	if (a != b) a = jump[a][0];
	return a;
}
void dfs(int pos, int par, int curLvl) {
	lvl[pos] = curLvl;
	jump[pos][0] = par;
	for (auto& el : paths[pos]) {
		if (el == par) continue;
		dfs(el, pos, curLvl+1);
	}
}
void init() {
	dfs(1, 1, 0);
	for (int i = 1; i <= n; i++) 
	for (int j = 1; j < M; j++) {
		int x = jump[i][j-1];
		jump[i][j] = jump[x][j-1];
	}
}
void update(int pos) {
	if (pos > 1) { // left
		int x = LCA(nums[pos], nums[pos-1]);
		int y = vals[pos-1];
		vals[pos-1] = x;
		if (y > 0) positions[y].erase(pos-1);
		positions[x].insert(pos-1);
	}
	if (pos + 1 <= m) { // right
		int x = LCA(nums[pos], nums[pos+1]);
		int y = vals[pos];
		vals[pos] = x;
		if (y > 0) positions[y].erase(pos);
		positions[x].insert(pos);
	}
}
signed main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		paths[a].pb(b);
		paths[b].pb(a);
	}
	for (int i = 1; i <= m; i++) cin >> nums[i];
	init();
	memset(vals, -1, sizeof(vals));
	for (int i = 1; i <= m; i++) {
		positions1[nums[i]].insert(i);
		update(i);
	}
	// for (int i = 1; i < m; i++) cout << vals[i] << " \n"[i==m-1];
	for (int i = 0; i < q; i++) {
		int a, b, c;
		cin >> a;
		if (a == 2) {
			cin >> a >> b >> c; // query from l to r, find V
			set <int>& cur = positions[c];
			set <int>& cur1 = positions1[c];
			auto it = cur.lower_bound(a);
			auto it1 = cur1.lower_bound(a);
			int x, y;
			if (it == cur.end() || *it > b) x = y = -1;
			else {
				x = *it; 
				y = x+1;
			}
			// if (x == -1) cout << *it1 << '\n';
			// cout << a << ',' << b << ' ';
			// cout << c << ": ";
			// for (auto el : cur1) cout <<el << ' '; cout << "\n";
			if (x == -1 && it1 != cur1.end() && *it1 <= b) {
				x = y = *it1;
			}
			cout << x << ' ' << y << '\n';
		} else {
			// cout << "UPDATE\n";
			cin >> a >> b; // update 
			positions1[nums[a]].erase(a);
			nums[a] = b;
			positions1[nums[a]].insert(a);
			update(a);
		}
	}
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24516 KB n=5
2 Correct 11 ms 24564 KB n=100
3 Correct 12 ms 24572 KB n=100
4 Correct 13 ms 24548 KB n=100
5 Correct 11 ms 24568 KB n=100
6 Correct 11 ms 24564 KB n=100
7 Correct 12 ms 24548 KB n=100
8 Correct 14 ms 24568 KB n=100
9 Correct 12 ms 24564 KB n=100
10 Correct 12 ms 24576 KB n=100
11 Correct 12 ms 24524 KB n=100
12 Incorrect 12 ms 24596 KB Wrong output format.
13 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24516 KB n=5
2 Correct 11 ms 24564 KB n=100
3 Correct 12 ms 24572 KB n=100
4 Correct 13 ms 24548 KB n=100
5 Correct 11 ms 24568 KB n=100
6 Correct 11 ms 24564 KB n=100
7 Correct 12 ms 24548 KB n=100
8 Correct 14 ms 24568 KB n=100
9 Correct 12 ms 24564 KB n=100
10 Correct 12 ms 24576 KB n=100
11 Correct 12 ms 24524 KB n=100
12 Incorrect 12 ms 24596 KB Wrong output format.
13 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24516 KB n=5
2 Correct 11 ms 24564 KB n=100
3 Correct 12 ms 24572 KB n=100
4 Correct 13 ms 24548 KB n=100
5 Correct 11 ms 24568 KB n=100
6 Correct 11 ms 24564 KB n=100
7 Correct 12 ms 24548 KB n=100
8 Correct 14 ms 24568 KB n=100
9 Correct 12 ms 24564 KB n=100
10 Correct 12 ms 24576 KB n=100
11 Correct 12 ms 24524 KB n=100
12 Incorrect 12 ms 24596 KB Wrong output format.
13 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24516 KB n=5
2 Correct 11 ms 24564 KB n=100
3 Correct 12 ms 24572 KB n=100
4 Correct 13 ms 24548 KB n=100
5 Correct 11 ms 24568 KB n=100
6 Correct 11 ms 24564 KB n=100
7 Correct 12 ms 24548 KB n=100
8 Correct 14 ms 24568 KB n=100
9 Correct 12 ms 24564 KB n=100
10 Correct 12 ms 24576 KB n=100
11 Correct 12 ms 24524 KB n=100
12 Incorrect 12 ms 24596 KB Wrong output format.
13 Halted 0 ms 0 KB -