Submission #981671

#	Time	Username	Problem	Language	Result	Execution time	Memory
981671		IUA_Hasin	Rainforest Jumps (APIO21_jumps)	C++17	25 / 100	1090 ms	38908 KiB

jumps

#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<N; i++){
      if(H[i]!=i+1){
        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;
  } else {
    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)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:74:21: warning: unused variable 'temp2' [-Wunused-variable]
   74 |           ll temp1, temp2;
      |                     ^~~~~

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