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;
}
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
*/
Compilation message (stderr)
skyscraper.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main()
| ^~~~
/tmp/ccMVwtXb.o: in function `__tcf_0':
skyscraper.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `vec' defined in .bss section in /tmp/ccMVwtXb.o
/tmp/ccMVwtXb.o: in function `bfs()':
skyscraper.cpp:(.text+0x2f6): relocation truncated to fit: R_X86_64_PC32 against symbol `vec' defined in .bss section in /tmp/ccMVwtXb.o
skyscraper.cpp:(.text+0x353): relocation truncated to fit: R_X86_64_PC32 against symbol `vec' defined in .bss section in /tmp/ccMVwtXb.o
/tmp/ccMVwtXb.o: in function `main':
skyscraper.cpp:(.text.startup+0xb): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x15): relocation truncated to fit: R_X86_64_PC32 against symbol `vec' defined in .bss section in /tmp/ccMVwtXb.o
skyscraper.cpp:(.text.startup+0x47): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x4e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x8f): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0xd8): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x198): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status