Submission #981601

#	Time	Username	Problem	Language	Result	Execution time	Memory
981601		IUA_Hasin	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4099 ms	498636 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

#define ll                          long long

using namespace std;

const ll M = 2e5+10;

vector<ll> graph[M];
set<pair<ll, ll>> indlevel;
map<pair<ll, ll>, ll> valevel;
//vector<set<ll>> inconnected[M];
vector<ll> outconnected[M];
//ll curr_level[M];
//ll vis[M][M];
map<pair<ll, ll>, ll> vis;
vector<ll> H2;


void init(int N, std::vector<int> H) {
    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];
        //cout << temp1 << " " << val << " " << 65 << endl;
        vis[{val, temp1}] = 1;
        outconnected[temp1].push_back(val);
        indlevel.insert({val, temp1});
        valevel[{val, temp1}] = 1;

        for(auto u : outconnected[val]){
            if(vis[{u, temp1}]==0){
            indlevel.insert({u, temp1});
            valevel[{u, temp1}] = valevel[{u, val}]+1;
            vis[{u, temp1}] = 1;
            //cout << temp1 << " " << u << " " << 76 << endl;
            outconnected[temp1].push_back(u);
            }
        }

        }


        if(it2!=s.end()){
        temp1 = *it2;
        temp1 = H[temp1];
        //cout << temp1 << " " << val << " " << 84 << endl;
        vis[{val, temp1}] = 1;
        outconnected[temp1].push_back(val);
        indlevel.insert({val, temp1});
        valevel[{val, temp1}] = 1;

        for(auto u : outconnected[val]){
            if(vis[{u, temp1}]==0){
            indlevel.insert({u, temp1});
            valevel[{u, temp1}] = valevel[{u, val}]+1;
            vis[{u, temp1}] = 1;
            //cout << temp1 << " " << u << " " << 97 << endl;
            outconnected[temp1].push_back(u);
            }
        }

        }

        // cout<<endl;
        // cout<<endl;

        auto itt = s.find(ind);
        s.erase(itt); 
    }

    // cout<<endl;
    // cout<<endl;
    // cout<<endl;

    // for(int i=1; i<=N; i++){
    //     cout << i << endl;
    //     for(int j=0; j<outconnected[i].size(); j++){
    //         cout << outconnected[i][j] << " ";
    //     }
    //     cout<<endl;
    //     cout<<endl;
    // }

}

int minimum_jumps(int A, int B, int C, int D) {
  ll status = -1;
  ll ans = INT_MAX;
  for(int i=A; i<=B; i++){
    for(int j=C; j<=D; j++){
      ll start = H2[i];
      ll end = H2[j];
      ll x = vis[{start, end}];
      if(x==1){
        ll temp = valevel[{start, end}];
        ans = min(temp, ans);
        status = 1;
      }
    }
  }
  if(status==-1){
    return -1;
  } else {
    return ans;
  }

}

Compilation message (stderr)

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

• 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