답안 #586078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586078 2022-06-29T20:01:06 Z jairRS 밀림 점프 (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);
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -