oj.uz

Submission #981661

# Submission time Handle Problem Language Result Execution time Memory
981661 2024-05-13T12:33:12 Z IUA_Hasin Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 588 ms 2040 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 78 ms 1636 KB Output is correct
4 Correct 588 ms 2024 KB Output is correct
5 Correct 547 ms 1148 KB Output is correct
6 Correct 552 ms 2040 KB Output is correct
7 Correct 443 ms 1532 KB Output is correct
8 Correct 552 ms 1880 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 78 ms 1636 KB Output is correct
4 Correct 588 ms 2024 KB Output is correct
5 Correct 547 ms 1148 KB Output is correct
6 Correct 552 ms 2040 KB Output is correct
7 Correct 443 ms 1532 KB Output is correct
8 Correct 552 ms 1880 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -