Submission #1172105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172105		baldwin_huang	Rainforest Jumps (APIO21_jumps)	C++20	23 / 100	726 ms	133620 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;
vector< vector<int> > binary_lifting(262144 + 1, vector<int>(32, -1)); // It tells you the 2^j ancestor of i.
vector< vector<int> > binary_lifting_x(262144 + 1, vector<int>(32, -1));
vector< vector<int> > binary_lifting_largest_left(262144 + 1, vector<int>(32, -1));

void init(int N, vector<int> H) {
	n = N;
	h = H;
	nodes = vector<node>(n); // It's a graph, has the index to the children.

	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;
	}

	// Create the binary_lift

	// Create the base ancestors;
	for (int i = 0; i < n; i++) {
		int greatest = -1;
		int ancestor = -1;
		if (nodes[i].left != -1 && greatest < H[nodes[i].left]) {
			greatest = H[nodes[i].left];
			ancestor = nodes[i].left;
		}
		if (nodes[i].right != -1 && greatest < H[nodes[i].right]) {
			greatest = H[nodes[i].right];
			ancestor = nodes[i].right;
		}
		binary_lifting[i][0] = ancestor;
	}

	for (int i = 1; i < 32; i++) {
		for (int j = 0; j < n; j++) {
			if (binary_lifting[j][i - 1] == -1) {
				binary_lifting[j][i] = -1;
			}
			else {
				binary_lifting[j][i] = binary_lifting[binary_lifting[j][i - 1]][i - 1];
			}
		}
	}

	// Bin lift for the Xs.
	for (int i = 0; i < n; i++) {
		int smallest = 1e9 + 10;
		int ancestor = -1;
		if (nodes[i].left != -1 && smallest > H[nodes[i].left]) {
			smallest = H[nodes[i].left];
			ancestor = nodes[i].left;
		}
		if (nodes[i].right != -1 && smallest > H[nodes[i].right]) {
			smallest = H[nodes[i].right];
			ancestor = nodes[i].right;
		}
		binary_lifting_x[i][0] = ancestor;
	}

	for (int i = 1; i < 32; i++) {
		for (int j = 0; j < n; j++) {
			if (binary_lifting_x[j][i - 1] == -1) {
				binary_lifting_x[j][i] = -1;
			}
			else {
				binary_lifting_x[j][i] = binary_lifting_x[binary_lifting_x[j][i - 1]][i - 1];
			}
		}
	}

	// Bin lift for the largest to the left
	for (int i = 0; i < n; i++) {
		binary_lifting_largest_left[i][0] = nodes[i].right;
	}

	for (int i = 1; i < 32; i++) {
		for (int j = 0; j < n; j++) {
			if (binary_lifting_largest_left[j][i - 1] == -1) {
				binary_lifting_largest_left[j][i] = -1;
			}
			else {
				binary_lifting_largest_left[j][i] = binary_lifting_largest_left[binary_lifting_largest_left[j][i - 1]][i - 1];
			}
		}
	}

	return;
}

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

	if (C != D) {
		return -1;
	}

	// Look for the starting point, aka, the new A.
	for (int i = 18; i >= 0; i--) {
		if (binary_lifting_largest_left[A][i] != -1 && binary_lifting_largest_left[A][i] <= B && h[binary_lifting_largest_left[A][i]] <= h[C] && (h[C] < h[binary_lifting_largest_left[A][i + 1]] || binary_lifting_largest_left[A][i + 1] == -1)) {
			A = binary_lifting_largest_left[A][i];
		}
	}	

	int ans = 0;
	int pos = A;

	// Find the Y that is <= C
	for (int i = 18; i >= 0; i--) {
		if (binary_lifting[pos][i] != -1 && h[binary_lifting[pos][i]] <= h[C] && (h[C] < h[binary_lifting[pos][i + 1]] || binary_lifting[pos][i + 1] == -1)) {
			pos = binary_lifting[pos][i];
			ans += 1<<i;
		}
	}		

	// Does the same but for the X value.
	
	for (int i = 18; i >= 0; i--) {
		if (binary_lifting_x[pos][i] != -1 && h[binary_lifting_x[pos][i]] <= h[C] && (h[C] < h[binary_lifting_x[pos][i + 1]] || binary_lifting_x[pos][i + 1] == -1)) {
			pos = binary_lifting_x[pos][i];
			ans += 1<<i;
		}
	}

	// Checks if the answer is valid

	if (pos == C) {
		return ans;
	}
	else {
		return -1;
	}
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19