Submission #1125303

#TimeUsernameProblemLanguageResultExecution timeMemory
1125303njoopJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
885 ms284572 KiB
#include <bits/stdc++.h> #define tiii tuple<int, int, int> using namespace std; int MXN = 30000; int n, m, dis[30001][175], b, p, d=174, st, en; vector<tiii> g[30001][175]; priority_queue<tiii, vector<tiii>, greater<tiii>> pq; void dijkstra() { pq.push({0, st, 0}); while(pq.size()) { int cd = get<0>(pq.top()); int cb = get<1>(pq.top()); int cp = get<2>(pq.top()); pq.pop(); if(cd > dis[cb][cp]) continue; for(auto i: g[cb][cp]) { int nd = cd+get<2>(i); int nb = get<0>(i); int np = get<1>(i); if(nd < dis[nb][np]) { dis[nb][np] = nd; pq.push({nd, nb, np}); } } } } int main() { cin >> n >> m; for(int i=0; i<sqrt(MXN); i++) { for(int j=0; j<n; j++) { if(j-i >= 0) { g[j-i][i].push_back({j, i, 1}); } if(j+i < n) { g[j+i][i].push_back({j, i, 1}); } g[j][i].push_back({j, 0, 0}); } } for(int i=0; i<30001; i++) { for(int j=0; j<175; j++) { dis[i][j] = 1e9; } } for(int i=0; i<m; i++) { cin >> b >> p; if(i == 0) st = b; if(i == 1) en = b; if(p >= sqrt(MXN)) { int cnt = 0; for(int j=b; j<n; j+=p) { g[b][d].push_back({j, 0, cnt}); cnt++; } cnt = 1; for(int j=b-p; j>=0; j-=p) { g[b][d].push_back({j, 0, cnt}); cnt++; } g[b][0].push_back({b, d, 0}); } else { g[b][0].push_back({b, p, 0}); } } dijkstra(); if(dis[en][0] == 1e9) cout << -1; else cout << dis[en][0]; 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...