제출 #341810

#제출 시각아이디문제언어결과실행 시간메모리
341810egod1537Jakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
1097 ms21612 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]; set<int> con[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; vit[doge[i].pos].insert(doge[i].range); } 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<int>& ncon = con[now.pos]; set<pi>& nV = V[now.pos]; for (int j = now.pos + now.range; j < n; j += now.range) { if (ncon.find(j) != ncon.end() || vit[j].size() == 0) continue; int dst = j - now.pos; nV.insert({ j, dst / now.range }); ncon.insert(j); if (vit[j].find(now.range) != vit[j].end()) break; } for (int j = now.pos - now.range; j >= 0; j -= now.range) { if (ncon.find(j) != ncon.end() || vit[j].size() == 0) continue; int dst = now.pos - j; nV.insert({ j, dst / now.range }); ncon.insert(j); if (vit[j].find(now.range) != vit[j].end()) 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...