///
/// ♪ Pizza mozzarella rella rella rella... ♪
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
const int N = 30'010;
int mod;
struct myset
{
int v[10000010+RAND_MAX][6] = {};
unsigned char sz[10000010+RAND_MAX] = {};
bool add(int x)
{
int y = x%mod;
Loop(i,0,sz[y])
if(v[y][i]==x)
return 0;
if(sz[y] == 6) exit(0);
v[y][sz[y]++] = x;
return 1;
}
};
myset d;
vector<int> P[N];
bool vis[N];
int n, m;
int bfs(int sv, int sp, int des)
{
if(sv == des) return 0;
vector<int> q, q2;
vis[sv] = 1;
for(auto p : P[sv]) if(d.add(sv<<15^p)) q.push_back(sv<<15^p);
if(d.add(sv<<15^sp)) q.push_back(sv<<15^sp);
for(int d = 0; q.size();)
{
for(ull i = 0; i < q.size(); ++i)
{
int v = q[i]>>15, p = q[i]&32767;
//cerr << v << ' ' << p << ": " << d << '\n';
int u = v+p;
if(u == des) return d+1;
if(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
u = v-p;
if(u == des) return d+1;
if(0 <= u && u < n)
{
if(!vis[u]){
vis[u] = 1;
for(auto p : P[u]) if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
if(::d.add(u<<15^p)) q2.push_back(u<<15^p);
}
}
q = q2;
q2.clear();
++d;
}
return -1;
}
bool isPrime(int n)
{
if(n%2 == 0) return n==2;
for(int d = 3; d*d <= n; d += 2)
if(n%d == 0)
return 0;
return 1;
}
int main()
{
srand(time(0));
for(;;){int x = 10000000+rand(); if(isPrime(x)){mod=x; break;}}
FAST;
cin >> n >> m;
int p, src, des, dmy;
cin >> src >> p;
cin >> des >> dmy;
P[des].push_back(dmy);
Loop(i,2,m)
{
int v, p;
cin >> v >> p;
P[v].push_back(p);
}
cout << bfs(src, p, des) << '\n';
}
Compilation message
skyscraper.cpp:27:19: warning: integer overflow in expression of type 'int' results in '-2137483639' [-Woverflow]
27 | int v[10000010+RAND_MAX][6] = {};
| ^
skyscraper.cpp:27:19: error: size '-2137483639' of array 'v' is negative
skyscraper.cpp:28:30: warning: integer overflow in expression of type 'int' results in '-2137483639' [-Woverflow]
28 | unsigned char sz[10000010+RAND_MAX] = {};
| ^
skyscraper.cpp:28:30: error: size '-2137483639' of array 'sz' is negative
