Submission #954262

#TimeUsernameProblemLanguageResultExecution timeMemory
954262colossal_pepeJakarta Skyscrapers (APIO15_skyscraper)C++17
10 / 100
1 ms600 KiB
#include <iostream> #include <vector> #include <queue> using namespace std; int n, m; vector<int> b, p; vector<vector<int>> v; int solve() { vector<int> dist(m, -1); queue<pair<int, int>> q[2]; dist[b[0]] = 0; q[0].push({b[0], 0}); while ((q[0].size() or q[1].size()) and dist[1] == -1) { int o = q[0].empty(); auto [i, j] = q[o].front(); q[o].pop(); while (not v[i].empty()) { dist[v[i].back()] = dist[j] + (abs(i - b[j]) / p[j]); q[0].push({i, v[i].back()}); v[i].pop_back(); } if (i + p[j] < n) q[1].push({i + p[j], j}); if (i - p[j] >= 0) q[1].push({i - p[j], j}); } return dist[1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; v.resize(n), b.resize(m), p.resize(m); cin >> b[0] >> p[0]; for (int i = 1; i < m; i++) { cin >> b[i] >> p[i]; v[b[i]].push_back(i); } cout << solve() << '\n'; 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...