Submission #960470

#TimeUsernameProblemLanguageResultExecution timeMemory
960470BlagojJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1028 ms49980 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 30010; int n, m; map<int, ll> best[mxn]; vector<int> val[mxn]; int spot[mxn], jump[mxn]; int dx[] = {-1, 1}; void solve() { priority_queue<pair<ll, pair<int, int>>> pq; pq.push({0, {spot[0], jump[0]}}); best[spot[0]][jump[0]] = 0; while (pq.size()) { ll dist = -pq.top().first, pos = pq.top().second.first, pwr = pq.top().second.second; pq.pop(); for (auto x : val[pos]) { if (!best[pos].count(jump[x])) best[pos][jump[x]] = 1e18; if (dist < best[pos][jump[x]]) { best[pos][jump[x]] = dist; pq.push({-dist, {pos, jump[x]}}); } } for (int d = 0; d < 2; d++) { int newPos = pos + pwr * dx[d]; if (0 <= newPos && newPos < n) { if (!best[newPos].count(pwr)) best[newPos][pwr] = 1e18; if (dist + 1 < best[newPos][pwr]) { best[newPos][pwr] = dist + 1; pq.push({-best[newPos][pwr], {newPos, pwr}}); } } } } ll ans = 1e18; for (auto x : best[spot[1]]) ans = min(ans, x.second); cout << (ans != 1e18 ? ans : -1); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 0; i < m; i++) { cin >> spot[i] >> jump[i]; val[spot[i]].push_back(i); } solve(); }
#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...