Submission #938951

#TimeUsernameProblemLanguageResultExecution timeMemory
938951XiaoyangJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms1500 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second #define pll pair<ll,ll> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl; #define MP make_pair #define rep(i,a,b) for(ll i=a;i<b;i++) #define ALL(x) x.begin(),x.end() #define endl "\n" const ll inf=1e18; const ll maxn=33333; vector<pll>alist[maxn]; ll b[maxn],p[maxn]; ll dist[maxn]; priority_queue<pll,vector<pll>,greater<pll>>s; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n,m;cin>>n>>m; rep(i,0,m){ cin>>b[i]>>p[i]; ll hop=0; for(ll j=b[i]-p[i];j>=0;j-=p[i])alist[b[i]].pb(MP(++hop,j)); hop=0; for(ll j=b[i]+p[i];j<n;j+=p[i])alist[b[i]].pb(MP(++hop,j)); } rep(i,0,maxn)dist[i]=inf; dist[0]=0; s.push(MP(0,0)); while(!s.empty()){ auto u=s.top(); s.pop(); if(u.fi!=dist[u.se])continue; for(auto x:alist[u.se]){ if(dist[u.se]+x.fi<dist[x.se]){ dist[x.se]=dist[u.se]+x.fi; s.push(MP(dist[x.se],x.se)); } } } if(dist[1]==inf)cout<<-1<<endl; else cout<<dist[1]<<endl; 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...