Submission #404538

#TimeUsernameProblemLanguageResultExecution timeMemory
404538sadJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
104 ms56472 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back using namespace std; int n,m; const int N=2009; int vis[N][N],a[N][N],yes[N]; vector<pair<int,int>>v[N]; ll dis[N]; priority_queue<pair<ll,int>>q; void go(int x,int y) { for(int i=x+y;i<n;i+=y) { if(vis[x][i]==1)continue; vis[x][i]=1; int z=i-x;z/=y; v[x].pb({i,z}); } for(int i=x-y;i>-1;i-=y) { if(vis[x][i]==1)continue; vis[x][i]=1; int z=x-i;z/=y; v[x].pb({i,z}); } } int main() {int ww=0; cin>>n>>m;int w=0; for(int i=0;i<m;i++) { int x,y;cin>>x>>y; if(i==0)w=x; if(i==1)ww=x; a[x][y]=1; }int MX=2009; for(int i=0;i<n;i++) { for(int j=MX;j>-1;j--) { if(a[i][j]==0)continue; go(i,j); } } q.push({0,w});for(int i=0;i<n;i++)dis[i]=1e16; while(!q.empty()) { pair<int,int>x=q.top(); q.pop(); if(yes[x.se]==1)continue; yes[x.se]=1; dis[x.se]=-x.fi; for(auto it:v[x.se]) { if(yes[it.fi])continue; if(dis[x.se]+it.se>=dis[it.fi])continue; dis[it.fi]=dis[x.se]+it.se; q.push({-dis[it.fi],it.fi}); } } if(yes[ww]==0) { cout<<-1;return 0; }cout<<dis[ww];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...