제출 #813461

#제출 시각아이디문제언어결과실행 시간메모리
813461JuanJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms980 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize (03) #define int long long #define pb push_back #define pii pair<int,int> #define all(x) x.begin(),x.end() const int maxn = 3e4 + 5, INF = 0x3f3f3f3f; vector<int> doges[maxn]; int dist[maxn]; priority_queue<pii, vector<pii>, greater<pii>> pq; int32_t main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int bi, pi; cin >> bi >> pi; doges[bi].pb(pi); } for(int i = 0; i < n; i++){ sort(all(doges[i])); doges[i].erase(unique(all(doges[i])), doges[i].end()); // cout << doges[i].size() << endl; } for(int i = 0; i < n; i++) dist[i] = INF; pq.push({0,0}); dist[0] = 0; while(pq.size()){ auto[d,u] = pq.top(); pq.pop(); if(dist[u]<d) continue; // cout << u << ": " << dist[u] << endl; if(u==1) continue; for(int x : doges[u]){ for(int i = u+x; i < n; i+=x){ int wv = (i-u)/x; if(dist[i] > dist[u]+wv) dist[i] = dist[u]+wv, pq.push({dist[i], i}); } for(int i = u-x; i >= 0; i-=x){ int wv = (u-i)/x; if(dist[i] > dist[u]+wv) dist[i] = dist[u]+wv, pq.push({dist[i], i}); } } } if(dist[1] == INF) cout << -1; else cout << dist[1]; cout << '\n'; }
#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...