Submission #341808

#TimeUsernameProblemLanguageResultExecution timeMemory
341808egod1537Jakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
400 ms262148 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; typedef pair<int, int> pi; #define to first #define cost second #define pos first #define range second struct Q { int pos, cost; }; bool operator<(const Q& a, const Q& b) { return a.cost > b.cost; } vector<pi> V[30001]; int dst[30001]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); memset(dst, INF, sizeof(dst)); int n, m; cin >> n >> m; vector<pi> doge(m); vector<int> posdoge(n + 1, -1); int s = 0, e = 0; for (int i = 0; i < m; i++) { cin >> doge[i].pos >> doge[i].range; if (i == 0) s = doge[i].pos; if (i == 1) e = doge[i].pos; } for (int i = 0; i < m; i++) { pi& now = doge[i]; for (int j = now.pos + now.range; j < n; j += now.range) { int dst = j - now.pos; V[now.pos].push_back({ j, dst / now.range }); } for (int j = now.pos - now.range; j >= 0; j -= now.range) { int dst = now.pos - j; V[now.pos].push_back({ j, dst / now.range }); } } priority_queue<Q> pq; pq.push({ s, 0 }); while (!pq.empty()) { Q top = pq.top(); pq.pop(); if (top.pos == e) { cout << top.cost; return 0; } for (pi w : V[top.pos]) { if (dst[w.to] > top.cost + w.cost) { dst[w.to] = top.cost + w.cost; pq.push({ w.to, dst[w.to] }); } } } 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...