| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 405871 | A_D | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#define int long long
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int N=3e4;
vector<int> vec[N];
int vis[N][N];
int dis,st,n;
set<int> stt;
deque<ii> deq;
bool in(int x)
{
return 0<=x && x<n;
}
void fix(int v,int w)
{
if(in(v+w)&&(vis[v+w][w]>vis[v][w]+1||vis[v+w][w]==-1)){
// cout<<5<<endl;
vis[v+w][w]=vis[v][w]+1;
deq.push_back({v+w,w});
}
if(in(v-w)&&(vis[v-w][w]>vis[v][w]+1||vis[v-w][w]==-1)){
// cout<<5<<endl;
vis[v-w][w]=vis[v][w]+1;
deq.push_back({v-w,w});
}
}
int bfs()
{
deq.push_back({st,0});
while(deq.empty()==0){
int v=deq[0].F;
int w=deq[0].S;
deq.pop_front();
stt.insert(v);
if(v==dis)return vis[v][w];
fix(v,w);
// cout<<v<<" "<<w<<endl;
for(auto x:vec[v]){
vis[v][x]=min(vis[v][x],vis[v][w]);
fix(v,x);
// cout<<v<<" "<<x<<endl;
}
vec[v].clear();
}
return -1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m;
cin>>n>>m;
memset(vis,-1,sizeof(vis));
int x,y;
cin>>x>>y;
vis[x][0]=0;
vec[x].push_back(y);
st=x;
cin>>x>>y;
vec[x].push_back(y);
dis=x;
m-=2;
while(m--){
cin>>x>>y;
vec[x].push_back(y);
}
cout<<bfs()<<endl;
// for(auto x:stt)cout<<x<<" ";cout<<endl;
}
/*
5 3
0 2
1 1
4 1
*/