Submission #341816

#TimeUsernameProblemLanguageResultExecution timeMemory
341816egod1537Jakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1082 ms12652 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; } set<pi> V[30001]; set<int> vit[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); set<int> sx; 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; vit[doge[i].pos].insert(doge[i].range); sx.insert(doge[i].pos); } sort(doge.begin(), doge.end(), [](pi& a, pi& b) -> bool { if (a.range != b.range) return a.range > b.range; return a.pos < b.pos; }); for (int i = 0; i < m; i++) { pi& now = doge[i]; set<pi>& nV = V[now.pos]; auto itr = sx.find(now.pos); if (itr != sx.end() && next(itr) != sx.end()) { for (++itr; itr != sx.end(); itr++) { int x = *itr; int dst = x - now.pos; if (dst % now.range || vit[x].size() == 0) continue; nV.insert({ x, dst / now.range }); if (vit[x].find(now.range) != vit[x].end()) break; } } itr = sx.find(now.pos); if (itr != sx.begin()) { for (--itr; ; itr--) { int x = *itr; int dst = now.pos - x; if (dst % now.range || vit[x].size() == 0) { if (itr == sx.begin()) break; else continue; } nV.insert({ x, dst / now.range }); if (vit[x].find(now.range) != vit[x].end()) break; if (itr == sx.begin()) break; } } } 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...