#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define right sefudermano
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
if(b==0LL) return 1LL;
if(b==1LL) return mod(a,m);
ll k = mod(exp(a,b/2,m),m);
if(b&1LL){
return mod(a*mod(k*k,m),m);
}
else return mod(k*k,m);
}
int n,m;
const int N = 30100;
int b[N],p[N];
const int sq = 175;
int vis[N][sq + 15];
int dist[N][sq + 15];
vi aqui[N];
int mn[N];
const int inf = 1e9;
struct coisa{
int dist,cur,p;
coisa(){}
coisa(int a,int b,int c){
dist = a;
cur = b;
p = c;
}
bool operator<(const coisa& o)const{
return dist > o.dist;
}
};
#define pwr(x) (x>=sq ? sq + 1 : x)
const int infi = N * sq * 10;
vector<coisa> pq[infi + 10];
void djkistra(){
for(int i=0;i<N;i++){
mn[i] = inf;
for(int j=0;j<sq+10;j++)dist[i][j] = inf;
}
dist[b[0]][pwr(p[0])] =0;
mn[b[0]] = 0;
pq[0].pb(coisa(dist[b[0]][pwr(p[0])],b[0],p[0]));
int cur_d = 0;
while(true){
while(cur_d < infi and pq[cur_d].empty())cur_d++;
if(cur_d >= infi)break;
coisa c = pq[cur_d].back();
pq[cur_d].pop_back();
if(vis[c.cur][pwr(c.p)])continue;
vis[c.cur][pwr(c.p)]=1;
int d = dist[c.cur][pwr(c.p)];
int id = c.cur;
int cur = c.cur;
if(c.p < sq){
aqui[id].pb(c.p);
}
for(int x : aqui[id]){
if(x >= sq){
int t=0;
for(int l = cur-x;l>=0;l-=x){
t++;
if(mn[l] > d + t){
mn[l] = dist[l][sq+1] = d + t;
pq[mn[l]].pb(coisa(mn[l],l,x));
}
}
t=0;
for(int l = cur + x;l<n;l+=x){
t++;
if(mn[l] > d + t){
mn[l] = dist[l][sq + 1] = d + t;
pq[mn[l]].pb(coisa(mn[l],l,x));
}
}
}else{
dist[cur][x] = min(dist[cur][x],d);
if(cur - x >=0 and dist[cur-x][x] > d + 1){
dist[cur-x][x] = d + 1;
if(mn[cur-x] > d+1)mn[cur-x] = d+1;
if(!vis[cur-x][x])pq[d+1].pb(coisa(dist[cur-x][x],cur - x,x));
}
if(cur + x < n and dist[cur + x][x] > d + 1){
dist[cur + x][x] = d + 1;
if(mn[cur+x] > d+1)mn[cur+x] = d+1;
if(!vis[cur+x][x])pq[d+1].pb(coisa(dist[cur + x][x],cur + x,x));
}
}
}
aqui[id].clear();
}
int res = mn[b[1]];
if(res == inf)cout<<-1<<endl;
else cout << res << endl;
}
int32_t main(){
fastio;
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> b[i] >> p[i];
aqui[b[i]].pb(p[i]);
}
djkistra();
// Math -> gcd it all
// Did u check N=1? Did you switch N,M?
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
140 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
134 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
133 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
128 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
