Submission #839233

#TimeUsernameProblemLanguageResultExecution timeMemory
839233tch1cherinJakarta Skyscrapers (APIO15_skyscraper)C++17
22 / 100
113 ms226548 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INT_MAX LLONG_MAX const int MAX_N = 30000; const int C = 300; vector<pair<int, int>> G[MAX_N * C]; int B[MAX_N], P[MAX_N]; int D[MAX_N * C]; void connect(int u, int v, int w, bool directed = false) { G[u].push_back({v, w}); if (!directed) { G[v].push_back({u, w}); } } int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M; cin >> N >> M; for (int i = 0; i < M; i++) { cin >> B[i] >> P[i]; if (P[i] >= C) { for (int j = B[i] % P[i]; j < N; j += P[i]) { connect(B[i], j, abs(j - B[i]) / P[i], true); } } else { connect(B[i], B[i] + P[i] * N, 0, true); } } for (int i = 0; i < N; i++) { for (int power = 1; power < C; power++) { if (i - power >= 0) { connect(i + power * N, i + power * (N - 1), 1, true); connect(i + power * N, i - power, 1, true); } if (i + power < N) { connect(i + power * N, i + power * (N + 1), 1, true); connect(i + power * N, i + power, 1, true); } } } fill(D, D + MAX_N, INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; Q.push({D[B[0]] = 0, B[0]}); while (!Q.empty()) { auto [d, u] = Q.top(); Q.pop(); if (d > D[u]) { continue; } for (auto [v, w] : G[u]) { if (D[u] + w < D[v]) { Q.push({D[v] = D[u] + w, v}); } } } cout << (D[B[1]] == INT_MAX ? -1 : D[B[1]]) << "\n"; }

Compilation message (stderr)

skyscraper.cpp:4: warning: "INT_MAX" redefined
    4 | #define INT_MAX LLONG_MAX
      | 
In file included from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from skyscraper.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...