Submission #1265355

#TimeUsernameProblemLanguageResultExecution timeMemory
1265355canhnam357Jakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> p(n); int f, s, z; for (int i = 0; i < m; i++) { int b, c; cin >> b >> c; if (i == 0 && b - c < 0 && b + c >= n) { cout << -1; return 0; } if (i == 0) f = b, s = c; if (i == 1) z = b; if (c < n) p[b].push_back(c); } vector<vector<int>> d(n, vector<int>(n, INT_MAX)); d[f][s] = 0; deque<pair<int, int>> dq; dq.emplace_front(f, s); while (!dq.empty()) { auto [b, c] = dq.front(); dq.pop_front(); for (int i : p[b]) { if (d[b][c] < d[b][i]) { d[b][i] = d[b][c]; dq.emplace_front(b, i); } } if (b - c >= 0 && d[b - c][c] > d[b][c] + 1) { d[b - c][c] = d[b][c] + 1; dq.emplace_back(b - c, c); } if (b + c < n && d[b + c][c] > d[b][c] + 1) { d[b + c][c] = d[b][c] + 1; dq.emplace_back(b + c, c); } } int ans = *min_element(d[z].begin(), d[z].end()); if (ans == INT_MAX) ans = -1; cout << ans; return 0; }
#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...