Submission #1047886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047886		Maite_Morale	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4 ms	4696 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 2005
#define oo 1e18
#define pll pair<ll,ll>
#define F first
#define S second

const ll bts=20;
pll p[MAX],s[bts+10][MAX],t[bts+10][MAX];
vll v[MAX];
ll d[MAX],N,pass[MAX][MAX];
ll bfs(ll x,ll z){
   queue<ll> q;
   q.push(x);
   pass[z][x]=0;
   while(!q.empty()){
      ll u=q.front();q.pop();
      for(auto w : v[u]){
        if(pass[z][w]!=-1)continue;
        q.push(w);
        pass[z][w]=pass[z][u]+1;
      }
   }
}
pll query(ll x,ll y){
  if(x>y)return {0,N};
  ll c=log2l(abs(x-y)+1);
return max(t[c][x],t[c][y-(1LL<<c)+1]);
}
void init(int n, std::vector<int> H) {
    H.push_back(0);N=n;pll rt={0,n};
    for(int i=0;i<=n;i++){
      t[0][i]={H[i],i};
      rt=max(rt,t[0][i]);
    }
    for(int i=1;i<=bts;i++){
      for(int j=0;j<=n;j++){
        t[i][j]=max(t[i-1][j],t[i-1][j+(1LL<<(i-1))]);
      }
    }
    queue<pair<ll,pll>> q;
    q.push({rt.S,{0,n-1}});
    d[n]=0;s[0][n]={n,n};
    d[rt.S]=1;s[0][rt.S]={n,n};
    while(!q.empty()){
        pair<ll,pll> u=q.front();q.pop();
        pair<ll,pll> h1={query(u.S.F,u.F-1).S,{u.S.F,u.F-1}};
        if(h1.F!=n){
          d[h1.F]=d[u.F]+1;
          p[h1.F]={h1.S.F-1,h1.S.S+1};
          v[h1.F].push_back(p[h1.F].F);
          v[h1.F].push_back(p[h1.F].S);
          q.push(h1);
        }
        pair<ll,pll> h2={query(u.F+1,u.S.S).S,{u.F+1,u.S.S}};
        if(h2.F!=n){
          d[h2.F]=d[u.F]+1;
          p[h2.F]={h2.S.F-1,h2.S.S+1};
          v[h2.F].push_back(p[h2.F].F);
          v[h2.F].push_back(p[h2.F].S);
          q.push(h2);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            pass[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        bfs(i,i);
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    ll r=oo;
    for(int i=A;i<=B;i++){
        for(int j=C;j<=D;j++){
            if(pass[i][j]!=-1){
                r=min(r,pass[i][j]);
            }
        }
    }
    if(r==oo)return -1;
return r;
}

/*
7 4
3 2 1 6 4 5 7
4 4 6 6
1 1 5 5
0 0 2 2
5 5 6 6 
*/

Compilation message (stderr)

jumps.cpp: In function 'll bfs(ll, ll)':
jumps.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
   27 | }
      | ^

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19