Submission #531387

#TimeUsernameProblemLanguageResultExecution timeMemory
531387lunchboxJakarta Skyscrapers (APIO15_skyscraper)C++17
36 / 100
377 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define N 30000 #define INF 0x3f3f3f3f vector<int> ed[N]; vector<pair<int, int>> ej[N]; bool find(int j, int d) { auto it = lower_bound(ed[j].begin(), ed[j].end(), d); return it != ed[j].end() && *it == d; } int main() { static int dd[N]; int n, m, i, j, d, s, t; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; scanf("%d%d", &n, &m); s = t = -1; for (i = 0; i < m; i++) { scanf("%d%d", &j, &d); if (i == 0) s = j; else if (i == 1) t = j; ed[j].push_back(d); } for (i = 0; i < n; i++) sort(ed[i].begin(), ed[i].end()); for (i = 0; i < n; i++) { for (int d : ed[i]) { for (j = i + d; j < n; j += d) { ej[i].push_back({j, (j - i) / d}); if (find(j, d)) break; } for (j = i - d; j >= 0; j -= d) { ej[i].push_back({j, (i - j) / d}); if (find(j, d)) break; } } } memset(dd, 0x3f, n * sizeof *dd); dd[s] = 0; pq.push({0, s}); while (!pq.empty()) { i = pq.top().second; pq.pop(); for (auto [j, w] : ej[i]) { d = dd[i] + w; if (d < dd[j]) { dd[j] = d; pq.push({d, j}); } } } printf("%d\n", dd[t] == INF ? -1 : dd[t]); }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d%d", &j, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~
#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...