Submission #243346

#	Time	Username	Problem	Language	Result	Execution time	Memory
243346		neihcr7j	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	417 ms	262148 KiB

skyscraper

#include<bits/stdc++.h>

#define oo 1000000000
#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 < m; ++i)
    for (int  j = b[i] + p[i]; j < n; j += p[i]) {
      g[b[i]].push_back({j, (j - b[i]) / p[i]});
      if (s[j].find(p[i]) != s[j].end())
        break;
    }

  for (int i = 0; i < m; ++i)
    for (int  j = b[i] - p[i]; j >= 0; j -= p[i]) {
      g[b[i]].push_back({j, (b[i] - j) / p[i]});
      if (s[j].find(p[i]) != s[j].end())
        break;
    }

  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 u = p.top().second; p.pop();

    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: 0 / 21
• Subtask 5: 0 / 43