Submission #566899

#TimeUsernameProblemLanguageResultExecution timeMemory
566899TurkhuuRainforest Jumps (APIO21_jumps)C++17
33 / 100
4085 ms23852 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++){ a[i]--; } vector<int> idx(n); for(int i = 0; i < n; i++){ idx[a[i]] = i; } set<int> s; for(int i = n - 1; i >= 0; i--){ auto j = s.lower_bound(idx[i]); if(j != s.end()){ g[idx[i]].push_back(*j); } if(j != s.begin()){ g[idx[i]].push_back(*prev(j)); } s.insert(idx[i]); } } 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...