Submission #243363

#	Time	Username	Problem	Language	Result	Execution time	Memory
243363		neihcr7j	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	312 ms	63712 KiB

skyscraper

#include<bits/stdc++.h>

#define oo 100000000
#define maxn 30004

using namespace std;
typedef long long ll;

int n, m;

int b[maxn], p[maxn];
vector < pair < int, int > > g[maxn];

set < int > s[maxn];

int d[maxn];

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> n >> m;

  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
    s[b[i]].insert(p[i]);
  }

  for (int i = 0; i < n; ++i)
    for (auto p : s[i]) {
      for (int j = 1; i + j * p < n; ++j) {
        g[i].push_back({i + j * p, j});
        if (s[i + j * p].count(p))
          break;
      }
      for (int j = 1; i - j * p >= 0; ++j) {
        g[i].push_back({i - j * p, j});
        if (s[i - j * p].count(p))
          break;
      }
    }

  for (int i = 0; i < n; ++i)
    random_shuffle(g[i].begin(), g[i].end());

  priority_queue < pair < int, int > > p;

  fill(d, d + n + 1, oo);

  d[b[0]] = 0;

  p.push({0, b[0]});

  while (!p.empty()) {
    int dist = p.top().first, u = p.top().second; p.pop();

    if (d[u] != -dist) continue;

    for (auto i : g[u]) {
      int v = i.first, w = i.second;

      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        p.push({-d[v], v});
      }
    }
  }

  cout << (d[b[1]] == oo ? -1 : d[b[1]]);

  return 0;
}

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