Submission #506208

#	Time	Username	Problem	Language	Result	Execution time	Memory
506208		Abrar_Al_Samit	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	532 ms	2424 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
const int MX = 2001;
int n, m;
map<int,int>nodes[MX];
priority_queue<pair<int,int>>pq;
int dist[MX];
bool vis[MX];
vector<int>dvs[MX];

void PlayGround() {
  cin >> n >> m;
  for(int dv=1; dv<=n; ++dv) {
    for(int i=1; dv*i<=n; ++i) {
      dvs[dv*i].push_back(dv);
    }
  }

  int b[2];
  for(int i=0; i<m; ++i) {
    int _b, p;
    cin >> _b >> p;
    if(i<2) {
      b[i] = _b;
    }
    nodes[_b][p] = 1;
  }
  for(int i=0; i<n; ++i) {
    dist[i] = INF;
  }
  dist[b[1]] = 0;
  pq.emplace(0, b[1]);
  while(!pq.empty()) {
    int d, v;
    tie(d, v) = pq.top();
    d = -d;
    pq.pop();
    if(vis[v]) continue;
    vis[v] = 1;

    for(int i=0; i<n; ++i) if(i!=v) {
      int gap = abs(i-v);
      int need = INF;
      for(int dv : dvs[gap]) {
        if(nodes[i].count(dv)) {
          need = min(need, gap/dv);
        }
      }
      if(d+need<dist[i]) {
        dist[i] = d+need;
        pq.emplace(-dist[i], i);
      }
    }
  }

  if(dist[b[0]]==INF) {
    dist[b[0]] = -1;
  }

  cout << dist[b[0]] << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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