Submission #1187299

#TimeUsernameProblemLanguageResultExecution timeMemory
1187299WarinchaiJakarta Skyscrapers (APIO15_skyscraper)C++20
10 / 100
17 ms39568 KiB
#include<bits/stdc++.h> using namespace std; map<pair<short,short>,vector<short>>mp; int up1[2000005]; int up2[2000005]; int down1[2000005]; int down2[2000005]; int hor[2000005]; int dis[2000005]; int inf=1e9; int have[30005]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,m;cin>>n>>m; int st=0,en=0; for(int i=0;i<m;i++){ int b,p;cin>>b>>p; if(i==0)st=b; if(i==1)en=b; if(i!=1)mp[{b%p,p}].push_back(b); have[b]++; } for(int i=0;i<2e6;i++)up1[i]=up2[i]=down1[i]=down2[i]=hor[i]=-1; int id=n-1; for(auto x:mp){ int cur=x.first.first; int p=x.first.second; for(auto b:x.second)up1[b]=id+(b-cur)/p+1; for(cur;cur<n;cur+=p){ id++; if(have[cur])down1[id]=cur; if(cur!=x.first.first)hor[id-1]=id; } cur=x.first.first; for(auto b:x.second)up2[b]=id+(b-cur)/p+1; for(cur;cur<n;cur+=p){ id++; if(have[cur])down2[id]=cur; if(cur!=x.first.first)hor[id]=id-1; } } mp.clear(); for(int i=0;i<=id;i++)dis[i]=inf; deque<pair<int,int>>dq; dq.push_back({0,st}); while(!dq.empty()){ auto [d,u]=dq.front(); //cerr<<u<<" "<<d<<"\n"; dq.pop_front(); if(d>=dis[u])continue; dis[u]=d; if(u==en)break; if(up1[u]!=-1)dq.push_front({d,up1[u]}); if(up2[u]!=-1)dq.push_front({d,up2[u]}); if(down1[u]!=-1)dq.push_front({d,down1[u]}); if(down2[u]!=-1)dq.push_front({d,down2[u]}); if(hor[u]!=-1)dq.push_back({d+1,hor[u]}); } if(dis[en]==inf)cout<<-1; else cout<<dis[en]; }
#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...