제출 #586078

#제출 시각아이디문제언어결과실행 시간메모리
586078jairRS밀림 점프 (APIO21_jumps)C++17
0 / 100
4014 ms23200 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...