Submission #744387

#TimeUsernameProblemLanguageResultExecution timeMemory
744387khoquennguoiminhthuongJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
453 ms143956 KiB
#include<bits/stdc++.h> using namespace std; vector<pair<int,int>>g[1500005]; int n,m; int s,t; long long d[1500005]; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>m; for(int i=1;i<=m;i++) { int b,p;cin>>b>>p; b++; if(i==1)s=b; if(i==2)t=b; if(p>30){for(int j=b-p;j>=1;j-=p){g[b].push_back({j,(b-j)/p});} for(int j=b+p;j<=n;j+=p){g[b].push_back({j,(j-b)/p});} } else { g[b].push_back({n+(b-1)*30+p,0}); } } for(int i=1;i<=n;i++) for(int j=1;j<=30;j++) { g[n+(i-1)*30+j].push_back({i,0}); } for(int i=1;i<=n;i++) for(int j=1;j<=30;j++) { if(i+j<=n){ g[n+(i-1)*30+j].push_back({n+(i+j-1)*30+j,1}); g[n+(i+j-1)*30+j].push_back({n+(i-1)*30+j,1}); } } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; for(int i=1;i<=n*40;i++)d[i]=1e18; d[s]=0; pq.push({0,s}); //cout<<s<<endl; //for(auto v:g[1])cout<<v.first<<endl; while(pq.size()) { int u=pq.top().second; pq.pop(); for(auto v:g[u]) { if(d[v.first]>d[u]+v.second){d[v.first]=d[u]+v.second;pq.push({d[v.first],v.first});} } } if(d[t]<1e18) cout<<d[t]; else cout<<-1; 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...