Submission #879075

#TimeUsernameProblemLanguageResultExecution timeMemory
879075PelmeniJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
607 ms13008 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; // #define int long long typedef pair<int, int> T; const int oo = 1e9 + 7, K = 30; const int mod = 998244353; void solve() { int n, m; cin >> n >> m; vector<vector<T>> g(n + 2); vector<vector<int>> doge(n + 1); int start, kon; for (int i = 0; i < m; i++) { int v, j; cin >> v >> j; if (i == 0) start = v; if (i == 1) kon = v; doge[v].emplace_back(j); } vector<int> dist(n + 2, oo); set<T> s; s.insert({0, start}); dist[start] = 0; while ((int) s.size()) { auto [d, v] = *s.begin(); s.erase(s.begin()); if (dist[v] < d) continue; auto popraw = [&](int what, int from, int c) { if (dist[what] > dist[from] + c) { dist[what] = dist[from] + c; s.insert({dist[what], what}); } }; for (auto j : doge[v]) { for (int u = v - j, k = 1; u >= 0; u -= j, k++) { popraw(u, v, k); } for (int u = v + j, k = 1; u < n; u += j, k++) { popraw(u, v, k); } } } int ans = dist[kon]; if (ans == oo) ans = -1; cout << ans << "\n"; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:26:15: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |     dist[start] = 0;
      |               ^
skyscraper.cpp:46:23: warning: 'kon' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     int ans = dist[kon];
      |                       ^
#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...