Submission #1165036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165036		baldwin_huang	밀림 점프 (APIO21_jumps)	C++20	21 / 100	4053 ms	4244 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

int n;
const int INF = 1e9;

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

vector<node> nodes;

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

	// // Precomputing the left value.
	// set<int> heights_l;
	// vector<int> last_val_l(n + 1, -1);
	// for (int i = 0; i < n; i++) {
	// 	auto it = heights_l.upper_bound(H[i]);
	// 	if (it != heights_l.end()) {
	// 		nodes[i].left = last_val_l[*it];
	// 	}
	// 	heights_l.insert(H[i]);
	// 	last_val_l[H[i]] = i;
	// }
	// // Precomputing the right values.
	// set<int> heights_r;
	// vector<int> last_val_r(n + 1, -1);
	// for (int i = n - 1; i >= 0; i--) {
	// 	auto it = heights_r.upper_bound(H[i]);
	// 	if (it != heights_r.end()) {
	// 		nodes[i].right = last_val_r[*it];
	// 	}
	// 	heights_r.insert(H[i]);
	// 	last_val_r[H[i]] = i;
	// }

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

	// for (int i = 0; i < n; i++) {
	// 	cout << "Node " << i << ": " << nodes[i].left << ' ' << nodes[i].right << '\n';
	// }

	return;
}

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

	// Start the BFS

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

	// cout << A << ' ' << B << ' ' << nodes.size() << '\n';

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

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

		if (nodes[source].left != -1 && dist[nodes[source].left] == INF) {
			q.push(nodes[source].left);
			dist[nodes[source].left] = 1 + dist[source];
		}
		if (nodes[source].right != -1 && dist[nodes[source].right] == INF) {
			q.push(nodes[source].right);
			dist[nodes[source].right] = 1 + dist[source];
			// cout << (dist[source]) << '\n';
		}

		// cout << "Source: " << source << ' ' << dist[source] << '\n';
	}

	int smallest = INF;
	for (int i = C; i <= D; i++) {
		smallest = min(smallest, dist[i]);
	}

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

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