Submission #1170597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170597		baldwin_huang	Rainforest Jumps (APIO21_jumps)	C++20	Compilation error	0 ms	0 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> h;
const int INF = 1e9;

struct node {
	int left = -1;
	int right = -1;
};

vector<node> nodes;

void init(int N, vector<int> H) {
	n = N;
	h = H;
	nodes = vector<node>(n);

	for (int i = 1; i < n; i++) {
		int target = i - 1;
		while (H[target] <= H[i]) {
			if (target == -1) {
				break;
			}
			target = nodes[target].left;
		}
		nodes[i].left = target;
	}

	for (int i = n - 2; i >= 0; i--) {
		int target = i + 1;
		while (H[target] <= H[i]) {
			if (target == -1) {
				break;
			}
			target = nodes[target].right;
		}
		nodes[i].right = target;
	}

	// for (int i = 0; i < n; i++) {
	// 	int left = -1;
	// 	int right = -1;
	// 	for (int j = i - 1; j >= 0; j--) {
	// 		if (H[j] > H[i]) {
	// 			left = j;
	// 			break;
	// 		}
	// 	}
	// 	for (int j = i + 1; j < n; j++) {
	// 		if (H[j] > H[i]) {
	// 			right = j;
	// 			break;
	// 		}
	// 	}
	// 	nodes[i].left = left;
	// 	nodes[i].right = right;
	// }

	return;
}

int next_jump(int a, int c) {
	if (a == -1) {
		return -1;
	}
	int greatest = -1;
	int ancestor = -1;
	if (nodes[a].left != -1 && greatest < h[nodes[a].left] && h[nodes[a].left] <= h[c]) {
		greatest = h[nodes[a].left];
		ancestor = nodes[a].left;
	}
	if (nodes[a].right != -1 && greatest < h[nodes[a].right] && h[nodes[a].right] <= h[c]) {
		greatest = h[nodes[a].right];
		ancestor = nodes[a].right;
	}
	return ancestor;
}

int find_ancestor(int source, int distance) {
	int pos = source;
	for (int i = 31; i >= 0; i--) {
		if (distance & (1<<i)) {
			pos = binary_lifting[pos][i];
			if (pos == -1) {
				return -1;
			}
		}
 	}
	return pos;
}

int minimum_jumps(int A, int B, int C, int D) {

	// Start the BFS

	vector<int> dist(n + 10, INF);
	queue<int> q;

	for (int i = A; i <= B; i++) {
		dist[i] = 0;
		q.push(i);
	}

	while (!q.empty()) {
		int source = q.front(); q.pop();

		if (next_jump(source, C) != -1) {
			q.push(next_jump(source, C));
			dist[next_jump(source, C)] = 1 + dist[source];
		}
	}

	int smallest = INF;
	for (int i = C; i <= D; i++) {
		smallest = min(smallest, dist[i]);
	}
	
	if (next_jump(find_ancestor(A, smallest - 1), C) != C) {
	  return INF;
	}

	if (smallest == INF) {
		return -1;
	}
	return smallest;
}

Compilation message (stderr)

jumps.cpp: In function 'int find_ancestor(int, int)':
jumps.cpp:86:31: error: 'binary_lifting' was not declared in this scope
   86 |                         pos = binary_lifting[pos][i];
      |                               ^~~~~~~~~~~~~~