#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;
int lst[2*mxM], lc, rc;
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()
{
int cnt=0;
while(lc!=rc)
{
//assert(cnt<=mxM/3);
int now=lst[lc];
lc++;
cnt++;
if(Chk[now]) continue;
Chk[now]=true;
if(now<=N)
{
for(int nxt : out[now])
{
if(!Chk[nxt] && dis[nxt]<=dis[now]) continue;
dis[nxt]=dis[now];
lst[--lc]=nxt;
Chk[nxt]=true;
}
}
else
{
if(l[now]!=-1)
{
if(!Chk[l[now]] && dis[l[now]]>dis[now]+1)
{
dis[l[now]]=dis[now]+1;
lst[rc++]=l[now];
//lst.push_back(l[now]);
}
}
if(r[now]!=-1)
{
if(!Chk[r[now]] && dis[r[now]]>dis[now]+1)
{
dis[r[now]]=dis[now]+1;
lst[rc++]=r[now];
//lst.push_back(r[now]);
}
}
if(!Chk[in[now]] && dis[in[now]]>dis[now])
{
dis[in[now]]=dis[now];
lst[--lc]=in[now];
Chk[in[now]]=true;
//lst.push_front(in[now]);
}
}
}
}
int main()
{
gibon
cin >> N >> M;
idx=N+1;
BP.resize(M);
for(int i=0;i<M;i++)
{
cin >> BP[i].fir >> BP[i].sec;
BP[i].fir++;
if(i==0) X=BP[i].fir;
if(i==1) Y=BP[i].fir;
}
sort(BP.begin(), BP.end(), cmp1);
int cur=0;
while(cur<M)
{
int ncur=cur;
bool jog=false;
for(int j=(BP[ncur].fir-1)%BP[ncur].sec+1;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++;
}
}
for(int i=0;i<idx;i++)
{
dis[i]=mxM;
}
dis[X]=0;
lst[mxM]=X;
lc=mxM, rc=mxM+1;
//assert(idx<=2*mxM/3);
zero_one_bfs();
if(dis[Y]==mxM) cout << -1;
else cout << dis[Y];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
