제출 #341797

#제출 시각아이디문제언어결과실행 시간메모리
341797egod1537Jakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
2 ms1260 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pi; #define to first #define cost second #define pos first #define range second struct Q { ll pos, cost; }; struct cmp { bool operator()(const Q& a, const Q& b) { return a.cost > b.cost; } }; vector<pi> V[30001]; ll dst[30001]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); fill(dst, dst + 30001, LLONG_MAX); 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; } sort(doge.begin(), doge.end()); for (int i = 0; i < m; i++) posdoge[doge[i].pos] = i; for (int i = 0; i < m; i++) { pi& now = doge[i]; for (int j = now.pos + now.range; j < n; j += now.range) { int idx = posdoge[j]; if (idx == -1) continue; ll dst = j - now.pos; V[i].push_back({ j, dst / now.range }); //if (now.range == doge[idx].range) break; } for (int j = now.pos - now.range; j >= 0; j -= now.range) { //int idx = posdoge[j]; //if (idx == -1) continue; ll dst = now.pos - j; V[now.pos].push_back({ j, dst / now.range }); //if (now.range == doge[idx].range) break; } } priority_queue<Q, vector<Q>, cmp> 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...