# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
981661 | IUA_Hasin | Rainforest Jumps (APIO21_jumps) | C++17 | 588 ms | 2040 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 "jumps.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll M = 2e3+10;
ll N2;
vector<ll> graph[M];
vector<ll> H2;
ll vis[M];
ll level[M][M];
ll status2;
void bfs(ll source){
queue<ll> q;
q.push(source);
vis[source] = 1;
level[source][source] = 0;
while(!q.empty()){
ll temp = q.front();
q.pop();
for(auto u : graph[temp]){
if(vis[u]==0){
q.push(u);
level[source][u] = level[source][temp]+1;
vis[u] = 1;
}
}
}
}
void init(int N, std::vector<int> H) {
ll stat = 1;
for(int i=0; i<N2-1; i++){
if(H2[i+1]!=H2[i]){
stat = -1;
break;
}
}
status2 = stat;
if(stat==-1){
N2 = N;
vector<ll> v[N+1];
for(int i=0; i<N; i++){
ll a = H[i];
v[a].push_back(i);
H2.push_back(a);
}
set<ll> s;
for(int i=0; i<N; i++){
s.insert(i);
}
for(int i=1; i<=N; i++){
if(i==N){
break;
}
ll ind = v[i][0];
ll val = H[ind];
//cout<<ind<<" "<<val<<endl;
auto it1 = s.lower_bound(ind);
auto it2 = s.upper_bound(ind);
it1--;
ll temp1, temp2;
if(it1!=s.end()){
temp1 = *it1;
temp1 = H[temp1];
graph[val].push_back(temp1);
}
if(it2!=s.end()){
temp1 = *it2;
temp1 = H[temp1];
graph[val].push_back(temp1);
}
auto itt = s.find(ind);
s.erase(itt);
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
level[i][j] = -1;
}
}
for(int i=1; i<=N; i++){
for(int j=0; j<=N; j++){
vis[j] = 0;
}
bfs(i);
}
}
}
int minimum_jumps(int A, int B, int C, int D) {
if(status2==1){
return C-B;
}
ll status = -1;
ll ans = M+100;
for(int i=A; i<=B; i++){
for(int j=C; j<=D; j++){
ll start = H2[i];
ll end = H2[j];
ll temp = level[start][end];
if(temp>=0){
status = 1;
ans = min(ans, temp);
}
}
}
// if(status2==1){
// return C-B;
// }
if(status==-1){
return -1;
} else {
return ans;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |