Submission #272741

#	Time	Username	Problem	Language	Result	Execution time	Memory
272741		toonewbie	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	202 ms	8312 KiB

skyscraper

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N = 30000, RTN = 200;
int n, m, dist[MAX_N], s, e;
bool ck[MAX_N][RTN], fvis[MAX_N];
struct st{
  int b, p, w;
  st(int _b, int _p, int _w)
    :b(_b), p(_p), w(_w){}
};
vector<int> adj[MAX_N];
queue<st> q;
int main(){
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    adj[a].push_back(b);
    if (i == 0) s = a;
    if (i == 1) e = a;
  }
  dist[e] = -1;
  q.push(st(s, 0, 0));
  while (!q.empty()){
    st h = q.front();
    q.pop();
    if (h.b < 0 || h.b >= n) continue;
    if (abs(h.p) < RTN){
      if (ck[h.b][abs(h.p)]) continue;
      ck[h.b][abs(h.p)] = true;
    }
    if (!fvis[h.b]){
      fvis[h.b] = true;
      dist[h.b] = h.w;
      for (auto t : adj[h.b]){
        q.push(st(h.b + t, t, h.w + 1));
        q.push(st(h.b - t, -t, h.w + 1));
      }
    }
    q.push(st(h.b + h.p, h.p, h.w + 1));
  }
  printf("%d", dist[e]);
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d %d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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