제출 #699969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699969		Abrar_Al_Samit	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	145 ms	63832 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
 
const int nax = 3e4 + 3;
const int INF = 1e9;
const long long pr = 1e9 + 9;
const int cax = 1e6 + 3;
 
int b[nax], p[nax];
vector<int>doges[nax];
 
vector<pair<long long,int>>dist[cax];
int get(int x, int y) {
  long long H = x * pr + y;
  int H2 = H % cax;
  for(auto x : dist[H2]) {
    if(x.first==H) return x.second;
  }
  return INF;
}
void put(int x, int y, int val) {
  long long H = x * pr + y;
  int H2 = H % cax;
  dist[H2].emplace_back(H, val);
  assert(dist[H2].size()<=5);
}
void PlayGround() {
  int n, m;
  cin>>n>>m;
 
  for(int i=0; i<m; ++i) {
    cin>>b[i]>>p[i];
    doges[b[i]].push_back(p[i]);
  }
 
  put(b[0], 0, 0);
 
  deque<tuple<int,int,int>>dq;
  dq.push_back({b[0], 0, 0});
 
  while(!dq.empty()) {
    auto x = dq.front();
    dq.pop_front();
    int ss, j, d;
    tie(ss, j, d) = x;
    if(d!=get(ss, j)) continue;
    if(ss==b[1]) {
      cout<<d<<'\n';
      return;
    }
 
 
    if(j==0) {
      for(int z : doges[ss]) {
        if(get(ss, z)>d) {
          put(ss, z, d);
          dq.emplace_front(ss, z, d);
        }
      }
    } else {
      if(ss+j<n) {
        if(get(ss+j, j)>d+1) {
          put(ss+j, j, d+1);
          dq.emplace_back(ss+j, j, d+1);
        }
        if(get(ss+j, 0)>d+1) {
          put(ss+j, 0, d+1);
          dq.emplace_back(ss+j, 0, d+1);
        }
      }
      if(ss-j>=0) {
        if(get(ss-j, j)>d+1) {
          put(ss-j, j, d+1);
          dq.emplace_back(ss-j, j, d+1);
        }
        if(get(ss-j, 0)>d+1) {
          put(ss-j, 0, d+1);
          dq.emplace_back(ss-j, 0, d+1);
        }
      }
    }
  }
  cout<<"-1\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43