Submission #45955

#	Time	Username	Problem	Language	Result	Execution time	Memory
45955		Just_Solve_The_Problem	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	286 ms	3512 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ok puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");

const int N = (int)3e4 + 7;
const int inf = (int)1e9 + 7;

vector < int > gr[N];
int n, m;
int dist[N];
int bb[N];

int bfs() {
  set < pii > s;
  memset(dist, 63, sizeof dist);
  s.insert(mk(0, bb[1]));
  dist[bb[1]] = 0;
  while (!s.empty()) {
    pii v = *s.begin();
    s.erase(s.begin());
    if (v.sc == bb[2]) return v.fr;
    for (int i = 0; i < sz(gr[v.sc]); i++) {
      if (i < sz(gr[v.sc]) - 1 && gr[v.sc][i] == gr[v.sc][i + 1]) continue;
      int d = gr[v.sc][i];
      for (int j = v.sc + d, k = 1; j <= n; j += d, k++) {
        if (v.fr + k < dist[j]) {
          s.erase(mk(dist[j], j));
          dist[j] = v.fr + k;
          s.insert(mk(dist[j], j));
        }
        if (binary_search(all(gr[j]), d)) break;
      }
      for (int j = v.sc - d, k = 1; j >= 1; j -= d, k++) {
        if (v.fr + k < dist[j]) {
          s.erase(mk(dist[j], j));
          dist[j] = v.fr + k;
          s.insert(mk(dist[j], j));
        }
        if (binary_search(all(gr[j]), d)) break;
      }
    }
  }
  return -1;
}

main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a++;
    bb[i] = a;
    gr[a].pb(b);
  }
  for (int i = 1; i <= n; i++) {
    sort(all(gr[i]));
  }
  printf("%d", bfs());
}

Compilation message (stderr)

skyscraper.cpp:59:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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