Submission #874513

#	Time	Username	Problem	Language	Result	Execution time	Memory
874513		chadmod	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1040 ms	1116 KiB

skyscraper

/**
 *    author:  NimaAryan
 *    created: 2023-11-17 08:21:07  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int N, M;
  cin >> N >> M;

  vector<int> B(M), P(M);
  for (int i = 0; i < M; ++i) {
    cin >> B[i] >> P[i];
  }

  vector<vector<int>> at(N);
  for (int i = 0; i < M; ++i) {
    at[B[i]].push_back(P[i]);
  }

  constexpr int inf = numeric_limits<int>::max();

  vector<int> dist(N, inf);
  dist[B[1]] = 0;

  vector<bool> vis(N);

  for (int it = 0; it < N; ++it) {
    int v = -1;
    for (int u = 0; u < N; ++u) {
      if (!vis[u] && (v == -1 || dist[u] < dist[v])) {
        v = u;
      }
    }
    if (v == -1 || dist[v] == inf) {
      break;
    }
    vis[v] = true;
    for (int u = 0; u < N; ++u) {
      if (vis[u]) {
        continue;
      }
      int d = abs(v - u);
      for (int p : at[u]) {
        if (d % p == 0) {
          dist[u] = min(dist[u], dist[v] + d / p);
        }
      }
    }
  }

  cout << (vis[B[0]] ? dist[B[0]] : -1) << "\n";

  return 0;
}

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