#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=30010;
const int mxM=7300000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N, M;
vector <pii> BP;
int l[mxM], r[mxM], in[mxM];
vector <int> out[mxN];
int idx;
int X, Y;
deque <int> lst;
int dis[mxM];
bool Chk[mxM];
bool cmp1(pii a, pii b)
{
if(a.sec!=b.sec) return a.sec<b.sec;
if(a.fir%a.sec!=b.fir%b.sec) return a.fir%a.sec<b.fir%b.sec;
return a.fir<b.fir;
}
void zero_one_bfs()
{
while(!lst.empty())
{
int now=lst.front();
lst.pop_front();
if(Chk[now]) continue;
Chk[now]=true;
if(now<N)
{
for(int nxt : out[now])
{
if(dis[nxt]>dis[now])
{
dis[nxt]=dis[now];
lst.push_front(nxt);
}
}
}
else
{
if(l[now]!=-1)
{
if(dis[l[now]]>dis[now]+1)
{
dis[l[now]]=dis[now]+1;
lst.push_back(r[now]);
}
}
if(r[now]!=-1)
{
if(dis[r[now]]>dis[now]+1)
{
dis[r[now]]=dis[now]+1;
lst.push_back(r[now]);
}
}
if(dis[in[now]]>dis[now])
{
dis[in[now]]=dis[now];
lst.push_front(in[now]);
}
}
}
}
int main()
{
gibon
cin >> N >> M;
idx=N;
BP.resize(M);
for(int i=0;i<M;i++)
{
cin >> BP[i].fir >> BP[i].sec;
if(i==0) X=BP[i].fir;
if(i==1) Y=BP[i].fir;
}
sort(BP.begin(), BP.end(), cmp1);
for(int i=0;i<mxM;i++) l[i]=r[i]=in[i]=-1;
int cur=0;
while(cur<M)
{
int ncur=cur;
bool jog=false;
for(int j=BP[ncur].fir%BP[ncur].sec;j<N;j+=BP[ncur].sec)
{
if(cur<M && BP[cur].fir==j && BP[cur].sec==BP[ncur].sec)
{
out[j].push_back(idx);
while(cur<M && BP[cur].fir==j && BP[cur].sec==BP[ncur].sec) cur++;
}
in[idx]=j;
if(!jog) jog=true;
else
{
l[idx]=idx-1;
r[idx-1]=idx;
}
idx++;
if(idx>=mxM) return 0;
}
}
for(int i=0;i<idx;i++)
{
dis[i]=MOD;
}
dis[X]=0;
lst.push_front(X);
zero_one_bfs();
if(dis[Y]==MOD) cout << -1;
else cout << dis[Y];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
123 ms |
175680 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
126 ms |
175596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
125 ms |
175644 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
123 ms |
175556 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
126 ms |
175580 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |