| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054371 | Gangsta | Rainforest Jumps (APIO21_jumps) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 1;
int dis[N], n1;
bool sub1 = 0;
vector <int> v[N];
priority_queue <pair<int,int>> pq;
void dij(int x){
pq.push({0,x});
dis[x] = 0;
while(!pq.empty()){
int a = pq.top().ss;
pq.pop();
for(auto i: v[a]){
if(dis[a] + i.ss < dis[i.ff]){
dis[i.ff] = dis[a] + i.ss;
pq.push({-dis[i.ff],i.ff});
}
}
}
}
int minimum_jumps(int a, int b, int c, int d){
int mn = 1e9;
for(int i = a; i <= b; i++){
for(int j = 1; j <= n1; j++) dis[j] = 0;
dij(i);
for(int j = c; j <= d; j++) mn = min(mn,dis[j]);
}
return mn;
}
void init(int n, vector <int> h){
n1 = n;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(h[j] > h[i]){
v[h[i]].pb(h[j]);
break;
}
}
for(int j = i-1; j >= 0; j--){
if(h[j] > h[i]){
v[h[i]].pb(h[j]);
break;
}
}
}
}
// int main(){
// int n, q;
// vector <int> v;
// cin >> n;
// for(int i = 0; i < n; i++){
// int x;
// cin >> x;
// v.pb(x);
// }
// init(n, v);
// cin >> q;
// while(q--){
// int a, b, c, d;
// cin >> a >> b >> c >> d;
// }
// }