제출 #369636

#제출 시각아이디문제언어결과실행 시간메모리
369636Bill_00Jakarta Skyscrapers (APIO15_skyscraper)C++14
22 / 100
1090 ms35176 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define mp make_pair #define pb push_back #define pp push #define MOD 1000000007 #define INF 1e18 #define N 30005 #define M 5000000 typedef long long ll; const ll c=174; using namespace std; ll b[N],p[N],pos[N],path[N]; bool vis[N]; set<ll>v[c][c]; int main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0) memset(pos,-1,sizeof(pos)); memset(path,-1,sizeof(path)); ll n,m; cin >> n >> m; for(ll i=0;i<m;i++){ cin >> b[i] >> p[i]; pos[b[i]]=i; for(ll j=1;j<c;j++){ v[j][b[i]%j].insert(i); } } priority_queue<pair<ll,ll> >pq; pq.push({0,0}); while(!pq.empty()){ ll cost=-pq.top().ff; ll doge_id=pq.top().ss; path[doge_id]=cost; pq.pop(); vis[doge_id]=1; if(p[doge_id]>=c){ for(ll i=b[doge_id]%p[doge_id];i<n;i+=p[doge_id]){ if(pos[i]!=-1){ if(vis[pos[i]]==0){ pq.push({-(cost+(abs(b[doge_id]-i))/p[doge_id]),pos[i]}); } } } } else{ for(ll i=1;i<c;i++){ v[i][b[doge_id]%i].erase(doge_id); } for(auto it=v[p[doge_id]][b[doge_id]%p[doge_id]].begin();it!=v[p[doge_id]][b[doge_id]%p[doge_id]].end();++it){ if(vis[*it]==0){ pq.push({-(cost+(abs(b[*it]-b[doge_id]))/p[doge_id]),*it}); } } } while(!pq.empty() && vis[pq.top().ss]==1) pq.pop(); } cout << path[1]; }
#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...