제출 #566884

#제출 시각아이디문제언어결과실행 시간메모리
566884Turkhuu밀림 점프 (APIO21_jumps)C++17
21 / 100
4051 ms14360 KiB
#include "jumps.h" #include <bits/stdc++.h> using namespace std; const int inf = 1000000000; int n; vector<int> a; vector<vector<int>> g; void init(int N, vector<int> H){ n = N, a = H; g.resize(n); for(int i = 0; i < n; i++){ int l = i - 1, r = i + 1; while(l >= 0 && a[l] <= a[i]) l--; while(r < n && a[r] <= a[i]) r++; if(l >= 0) g[i].push_back(l); if(r < n) g[i].push_back(r); } } int minimum_jumps(int A, int B, int C, int D){ queue<int> q; vector<int> d(n, inf); for(int i = A; i <= B; i++){ d[i] = 0; q.push(i); } while(!q.empty()){ int i = q.front(); q.pop(); if(C <= i && i <= D){ return d[i]; } for(int j : g[i]){ if(d[i] + 1 < d[j]){ d[j] = d[i] + 1; q.push(j); } } } return -1; }
#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...