Submission #1265361

#TimeUsernameProblemLanguageResultExecution timeMemory
1265361canhnam357Jakarta Skyscrapers (APIO15_skyscraper)C++20
57 / 100
1099 ms82428 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) f = b, s = c; if (i == 1) z = b; if (c > n) c = n; p[b].push_back(c); } vector<unordered_map<int, int>> d(n); d[f][s] = 0; deque<pair<int, int>> dq; dq.emplace_front(f, s); while (!dq.empty()) { auto [b, c] = dq.front(); if (b == z) { cout << d[b][c]; return 0; } dq.pop_front(); for (int i : p[b]) { if (!d[b].count(i) || d[b][c] < d[b][i]) { d[b][i] = d[b][c]; dq.emplace_front(b, i); } } if (b - c >= 0 && (!d[b - c].count(c) || 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].count(c) || d[b + c][c] > d[b][c] + 1)) { d[b + c][c] = d[b][c] + 1; dq.emplace_back(b + c, c); } } cout << -1; 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...