제출 #1196243

#제출 시각아이디문제언어결과실행 시간메모리
1196243ezzzayJakarta Skyscrapers (APIO15_skyscraper)C++20
0 / 100
1 ms584 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define int long long const int N=4000; bool vis[N]; vector<int>vc[N]; vector<pair<int,int>>v[N]; int X[N],P[N]; int dst[N][N]; signed main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++){ int x,p; cin>>x>>p; X[i]=x; P[i]=p; for(int j=1;j<=n;j++){ if(x-p*j>=0)v[x].pb({x-p*j,j}); if(x+p*j<n)v[x].pb({x+p*j,j}); } vc[x].pb(p); } dst[X[0]][P[0]]=1; queue<pair<int,int>>q ; q.push({X[0],P[0]}); while(!q.empty()){ auto [x,p]=q.front(); q.pop(); if(x+p<n){ for(auto a:vc[x+p]){ if(dst[x+p][a]==0){ dst[x+p][a]=dst[x][p]+1; q.push({x+p,a}); } } if(dst[x+p][p]==0){ dst[x+p][p]=dst[x][p]+1; q.push({x+p,p}); } } if(x-p>=0 and dst[x-p][p]==0){ for(auto a:vc[x-p]){ if(dst[x-p][a]==0){ dst[x-p][a]=dst[x][p]+1; q.push({x-p,a}); } } if(dst[x-p][p]==0){ dst[x-p][p]=dst[x][p]+1; q.push({x-p,p}); } } } int ans=1e17; for(int i=0;i<N;i++){ if(dst[X[1]][i])ans=min(ans,dst[X[1]][i]); } if(ans==1e17)ans=-1; cout<<ans-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...