Submission #699937

#	Time	Username	Problem	Language	Result	Execution time	Memory
699937		Abrar_Al_Samit	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	2 ms	2020 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

const int nax = 3e4 + 3;
const int INF = 1e9;

int b[nax], p[nax];
vector<int>doges[nax];

unordered_map<long long,int>dist;

int get(int x, int y) {
  long long H = x * 10000000LL + y;
  if(dist.find(H)!=dist.end()) return dist[H];
  return INF;
}
void put(int x, int y, int val) {
  long long H = x * 10000000LL + y;
  dist[H] = val;
}
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);

  queue<tuple<int,int,int>>q;
  q.push({b[0], 0, 0});

  int lim = n * 15;

  while(!q.empty()) {
    assert(dist.size()<lim);
    auto x = q.front();
    q.pop();
    int ss, j, d;
    tie(ss, j, d) = x;
    if(d!=get(ss, j)) continue;


    if(j==0) {
      for(int z : doges[ss]) {
        if(get(ss, z)>d) {
          put(ss, z, d);
          q.emplace(ss, z, d);
        }
      }
    } else {
      if(ss+j<n) {
        if(get(ss+j, j)>d+1) {
          put(ss+j, j, d+1);
          q.emplace(ss+j, j, d+1);
        }
        if(get(ss+j, 0)>d+1) {
          put(ss+j, 0, d+1);
          q.emplace(ss+j, 0, d+1);
        }
      }
      if(ss-j>=0) {
        if(get(ss-j, j)>d+1) {
          put(ss-j, j, d+1);
          q.emplace(ss-j, j, d+1);
        }
        if(get(ss-j, 0)>d+1) {
          put(ss-j, 0, d+1);
          q.emplace(ss-j, 0, d+1);
        }
      }
    }
  }
  int ans = get(b[1], 0);
  if(ans==INF) ans = -1;
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from skyscraper.cpp:1:
skyscraper.cpp: In function 'void PlayGround()':
skyscraper.cpp:38:23: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     assert(dist.size()<lim);
      |            ~~~~~~~~~~~^~~~

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