Submission #1210319

#TimeUsernameProblemLanguageResultExecution timeMemory
1210319k1r1t0Jakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
641 ms24576 KiB
#include <bits/stdc++.h> using namespace std; const int N = 31000; const int S = 174; const int INF = (int)(1e9); int dist[N][S], n, m; vector<int> p[N]; set<array<int, 3>> qq; void upd(int d, int w, int x, int y) { if (d + w < dist[x][y]) { qq.erase({dist[x][y], x, y}); dist[x][y] = d + w; qq.insert({dist[x][y], x, y}); } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; int pos1, pos2; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; x++; p[x].push_back(y); if (i == 1) pos1 = x; if (i == 2) pos2 = x; } for (int i = 1; i <= n; i++) for (int j = 0; j < S; j++) dist[i][j] = INF; dist[pos1][0] = 0; qq.insert({0, pos1, 0}); while (!qq.empty()) { auto [d, u, v] = *qq.begin(); qq.erase(qq.begin()); if (v == 0) { for (int j : p[u]) if (j >= S) { for (int k = u + j; k <= n; k += j) upd(d, (k - u) / j, k, 0); for (int k = u - j; k >= 1; k -= j) upd(d, (u - k) / j, k, 0); } else upd(d, 0, u, j); } else { if (u - v >= 1) upd(d, 1, u - v, v); if (u + v <= n) upd(d, 1, u + v, v); upd(d, 0, u, 0); } } int ans = dist[pos2][0]; if (ans == INF) ans = -1; cout << ans; }
#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...