Submission #1129131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129131		juicy	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	642 ms	25276 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define             fi  first
#define             se  second
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
  #include "debug.h"
#else
  #define debug(...)
#endif

template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

const int N = 3e4, B = 175, INF = 1e9;

int n, m;
int b[N], p[N], d[N][B];
vector<int> node[N];

void dijkstra() {
  using T = tuple<int, int, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  memset(d, 0x3f, sizeof(d));
  pq.push({d[b[0]][0] = 0, b[0], 0});
  while (pq.size()) {
    int c, u, p;
    tie(c, u, p) = pq.top();
    pq.pop();
    if (d[u][p] != c) {
      continue;
    }
    if (p == 0) {
      for (int x : node[u]) {
        if (x >= B) {
          for (int v = u - x, cnt = 1; v >= 0; v -= x, ++cnt) {
            if (minimize(d[v][0], c + cnt)) {
              pq.push({d[v][0], v, 0});
            }
          }
          for (int v = u + x, cnt = 1; v < n; v += x, ++cnt) {
            if (minimize(d[v][0], c + cnt)) {
              pq.push({d[v][0], v, 0});
            }
          }
        } else if (minimize(d[u][x], c)) {
          pq.push({d[u][x], u, x});
        }
      }
    } else {
      if (minimize(d[u][0], c)) {
        pq.push({d[u][0], u, 0});
      }
      for (int i = 0; i < 2; ++i) {
        int v = u + (i ? 1 : -1) * p;
        if (0 <= v && v < n && minimize(d[v][p], c + 1)) {
          pq.push({d[v][p], v, p});
        }
      }
    }
  }
}

void process() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
    node[b[i]].push_back(p[i]);
  }
  dijkstra();
  cout << (d[b[1]][0] >= INF ? -1 : d[b[1]][0]);
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  file("B");
  // int t; cin >> t; while (t--)
  process();
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:7:62: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:78:3: note: in expansion of macro 'file'
   78 |   file("B");
      |   ^~~~
skyscraper.cpp:7:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:78:3: note: in expansion of macro 'file'
   78 |   file("B");
      |   ^~~~

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