Submission #766363

#TimeUsernameProblemLanguageResultExecution timeMemory
766363linkretJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
650 ms26664 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e4 + 30, B = 200; const int inf = 2e9; int n, m; int dist[N][B]; bool bio[N]; vector<int> adj[N]; struct rec { int d, v, p; friend bool operator<(const rec& a, const rec& b) { if (a.d != b.d) return a.d < b.d; if (a.v != b.v) return a.v < b.v; return a.p < b.p; } }; /* 5 3 0 2 1 1 4 1 */ int main() { ios_base::sync_with_stdio(0); cin.tie(0); for(int i = 0; i < N; i++) { for(int j = 0; j < B; j++) { dist[i][j] = inf; } } cin >> n >> m; int s = 0, f = 0; for(int i = 0; i < m; i++) { int x, k; cin >> x >> k; adj[x].push_back(k); if(i == 0) s = x; if(i == 1) f = x; } // priority_queue<array<int,3>> q; priority_queue<rec> q; for(auto x : adj[s]) { if(x < B) { dist[s][x] = 0; q.push({dist[s][x], s, x}); } else { for(int k = 1; s + k * x < N; k++) { dist[s + k * x][0] = k; q.push({-dist[s + k * x][0], s + k * x, 0}); } for(int k = 1; s - k * x >= 0; k++) { dist[s - k * x][0] = k; q.push({-dist[s - k * x][0], s - k * x, 0}); } } } bio[s] = 1; while(!q.empty()) { auto top = q.top(); int d = top.d; int v = top.v; int p = top.p; q.pop(); d = -d; if(d > dist[v][p]) continue; if(!bio[v]) { for(auto x : adj[v]) { if(x < B) { dist[v][x] = d; q.push({-dist[v][x], v, x}); } else { for(int k = 1; v + k * x < n; k++) { if(dist[v + k * x][0] > d + k) { dist[v + k * x][0] = d + k; q.push({-dist[v + k * x][0], v + k * x, 0}); } } for(int k = 1; v - k * x >= 0; k++) { if(dist[v - k * x][0] > d + k) { dist[v - k * x][0] = d + k; q.push({-dist[v - k * x][0], v - k * x, 0}); } } } } bio[v] = 1; } if(v + p < N && dist[v + p][p] > d + 1) { dist[v + p][p] = d + 1; q.push({-dist[v + p][p], v + p, p}); } if(v - p >= 0 && dist[v - p][p] > d + 1) { dist[v - p][p] = d + 1; q.push({-dist[v - p][p], v - p, p}); } } int ans = inf; for(int k = 0; k < B; k++) ans = min(ans, dist[f][k]); if(ans == inf) ans = -1; cout << ans << '\n'; 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...