oj.uz

Submission #586078

# Submission time Handle Problem Language Result Execution time Memory
586078 2022-06-29T20:01:06 Z jairRS Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 23200 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 1;
vector<int> firstGreaterToTheRight;
vector<vector<int>> adj;

void init(int N, vector<int> H)
{
	stack<pair<int, int>> s;
	firstGreaterToTheRight = vector<int>(N, -1);
	adj = vector<vector<int>>(N);
	for (int i = N - 1; i >= 0; i--)
	{
		while (!s.empty() && s.top().first < H[i])
			s.pop();

		if (!s.empty())
			firstGreaterToTheRight[i] = s.top().second;

		s.push({H[i], i});
	}

	for (int i = 0; i < N; i++)
		if (firstGreaterToTheRight[i] != -1)
			adj[i].push_back(firstGreaterToTheRight[i]);
}

int minimum_jumps(int A, int B, int C, int D)
{
	int res = INF;

	queue<pair<int, int>> bfs;
	map<int, bool> vis;

	for (int L = A; L <= B; L++)
	{
		bfs.push({L, 0});
		vis[L] = true;
	}

	while (!bfs.empty())
	{
		pair<int, int> cur = bfs.front();
		bfs.pop();
		for (int a : adj[cur.first])
		{
			if (vis[a])
				continue;
			vis[a] = true;
			bfs.push({a, cur.second + 1});
			if (C <= a && a <= D)
				res = min(res, cur.second + 1);
		}
	}

	return (res == INF ? -1 : res);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Execution timed out 4014 ms 18096 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Incorrect 4 ms 208 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Incorrect 4 ms 208 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 42 ms 14764 KB Output is correct
6 Correct 74 ms 16544 KB Output is correct
7 Correct 16 ms 6968 KB Output is correct
8 Correct 80 ms 23200 KB Output is correct
9 Correct 11 ms 3152 KB Output is correct
10 Correct 48 ms 15888 KB Output is correct
11 Correct 204 ms 22156 KB Output is correct
12 Correct 221 ms 21644 KB Output is correct
13 Incorrect 152 ms 19792 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 270 ms 6312 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 270 ms 6312 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Execution timed out 4014 ms 18096 KB Time limit exceeded
4 Halted 0 ms 0 KB -