oj.uz

답안 #981601

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981601 2024-05-13T11:29:51 Z IUA_Hasin 밀림 점프 (APIO21_jumps) C++17
0 / 100
 4000 ms 498636 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Execution timed out 4099 ms 498636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 6 ms 9816 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 5 ms 10072 KB Output is correct
6 Incorrect 27 ms 11672 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 6 ms 9816 KB Output is correct
3 Correct 6 ms 9816 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 5 ms 10072 KB Output is correct
6 Incorrect 27 ms 11672 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 6 ms 9816 KB Output is correct
5 Execution timed out 4065 ms 356140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Execution timed out 4025 ms 332784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9688 KB Output is correct
2 Correct 5 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Execution timed out 4025 ms 332784 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9816 KB Output is correct
3 Execution timed out 4099 ms 498636 KB Time limit exceeded
4 Halted 0 ms 0 KB -