#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+2;
const int INF=2e9;
int n,m;
struct doge
{
int p,pos;
bool operator<(const doge& other)
{
if(pos!=other.pos)return pos<other.pos;
return p<=other.p;
}
}d[MAXN];
struct state
{
int pos,p,d;
bool operator<(state const& other)const
{
if(d!=other.d)return d>other.d;
return make_pair(p,pos)<make_pair(other.p,other.pos);
}
};
set<pair<int,int> >doges;
vector<int>doges1[MAXN];
vector<int>states;
unordered_map<int,int>dist;
int main()
{
srand(65435);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m;
for(int i=0;i<m;++i)
{
cin>>d[i].pos>>d[i].p;
doges.insert({d[i].p,d[i].pos%d[i].p});
doges1[d[i].pos].push_back(d[i].p);
}
for(auto t:doges)
{
for(int i=t.second;i<n;i+=t.first)
{
states.push_back(i*MAXN+t.first);
}
}
for(auto s:states)
{
dist[s]=INF;
}
priority_queue<state>pq;
pq.push({d[0].pos,d[0].p,0});
dist[d[0].pos*MAXN+d[0].p]=0;
while(!pq.empty())
{
state u=pq.top();pq.pop();
if(dist[u.pos*MAXN+u.p]<u.d)continue;
if(u.pos==d[1].pos&&u.p==d[1].p)break;
for(auto d1:doges1[u.pos])
{
if(clock()>0.9*CLOCKS_PER_SEC)
{
cout<<-1<<endl;
return 0;
}
if(d1==u.p)continue;
if(dist[u.pos*MAXN+d1]>u.d)
{
dist[u.pos*MAXN+d1]=u.d;
pq.push({u.pos,d1,u.d});
}
}
state v=u;
if(v.pos-v.p>=0)
{
v.pos-=v.p;
if(dist[v.pos*MAXN+v.p]>u.d+1)
{
v.d=u.d+1;
dist[v.pos*MAXN+v.p]=v.d;
pq.push(v);
}
}
v=u;
if(v.pos+v.p<n)
{
v.pos+=v.p;
if(dist[v.pos*MAXN+v.p]>u.d+1)
{
v.d=u.d+1;
dist[v.pos*MAXN+v.p]=v.d;
pq.push(v);
}
}
}
if(dist[d[1].pos*MAXN+d[1].p]==INF)
{
cout<<-1<<"\n";
}
else cout<<dist[d[1].pos*MAXN+d[1].p]<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1004 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1132 KB |
Output is correct |
11 |
Correct |
4 ms |
1388 KB |
Output is correct |
12 |
Correct |
13 ms |
1152 KB |
Output is correct |
13 |
Correct |
2 ms |
1132 KB |
Output is correct |
14 |
Correct |
58 ms |
1516 KB |
Output is correct |
15 |
Correct |
53 ms |
1516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1004 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1132 KB |
Output is correct |
11 |
Correct |
4 ms |
1388 KB |
Output is correct |
12 |
Correct |
13 ms |
1132 KB |
Output is correct |
13 |
Correct |
2 ms |
1132 KB |
Output is correct |
14 |
Correct |
58 ms |
1516 KB |
Output is correct |
15 |
Correct |
52 ms |
1516 KB |
Output is correct |
16 |
Correct |
2 ms |
1260 KB |
Output is correct |
17 |
Correct |
8 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1388 KB |
Output is correct |
19 |
Correct |
2 ms |
1388 KB |
Output is correct |
20 |
Correct |
3 ms |
1260 KB |
Output is correct |
21 |
Correct |
2 ms |
1260 KB |
Output is correct |
22 |
Correct |
2 ms |
1388 KB |
Output is correct |
23 |
Correct |
5 ms |
1388 KB |
Output is correct |
24 |
Correct |
11 ms |
1772 KB |
Output is correct |
25 |
Correct |
4 ms |
1644 KB |
Output is correct |
26 |
Correct |
2 ms |
1516 KB |
Output is correct |
27 |
Correct |
145 ms |
1516 KB |
Output is correct |
28 |
Correct |
16 ms |
2284 KB |
Output is correct |
29 |
Correct |
31 ms |
3700 KB |
Output is correct |
30 |
Correct |
7 ms |
1900 KB |
Output is correct |
31 |
Correct |
16 ms |
2924 KB |
Output is correct |
32 |
Correct |
11 ms |
2156 KB |
Output is correct |
33 |
Correct |
101 ms |
6404 KB |
Output is correct |
34 |
Correct |
88 ms |
6548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1004 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1132 KB |
Output is correct |
11 |
Correct |
4 ms |
1388 KB |
Output is correct |
12 |
Correct |
13 ms |
1132 KB |
Output is correct |
13 |
Correct |
2 ms |
1132 KB |
Output is correct |
14 |
Correct |
59 ms |
1516 KB |
Output is correct |
15 |
Correct |
51 ms |
1644 KB |
Output is correct |
16 |
Correct |
2 ms |
1260 KB |
Output is correct |
17 |
Correct |
8 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1388 KB |
Output is correct |
19 |
Correct |
2 ms |
1388 KB |
Output is correct |
20 |
Correct |
3 ms |
1408 KB |
Output is correct |
21 |
Correct |
2 ms |
1260 KB |
Output is correct |
22 |
Correct |
2 ms |
1388 KB |
Output is correct |
23 |
Correct |
5 ms |
1388 KB |
Output is correct |
24 |
Correct |
9 ms |
1772 KB |
Output is correct |
25 |
Correct |
4 ms |
1644 KB |
Output is correct |
26 |
Correct |
3 ms |
1516 KB |
Output is correct |
27 |
Correct |
145 ms |
1516 KB |
Output is correct |
28 |
Correct |
16 ms |
2284 KB |
Output is correct |
29 |
Correct |
31 ms |
3700 KB |
Output is correct |
30 |
Correct |
7 ms |
1900 KB |
Output is correct |
31 |
Correct |
16 ms |
2924 KB |
Output is correct |
32 |
Correct |
11 ms |
2156 KB |
Output is correct |
33 |
Correct |
101 ms |
6404 KB |
Output is correct |
34 |
Correct |
88 ms |
6400 KB |
Output is correct |
35 |
Correct |
372 ms |
7548 KB |
Output is correct |
36 |
Correct |
9 ms |
2284 KB |
Output is correct |
37 |
Correct |
122 ms |
10760 KB |
Output is correct |
38 |
Correct |
125 ms |
10884 KB |
Output is correct |
39 |
Correct |
53 ms |
10500 KB |
Output is correct |
40 |
Correct |
86 ms |
10756 KB |
Output is correct |
41 |
Correct |
307 ms |
11268 KB |
Output is correct |
42 |
Correct |
7 ms |
2028 KB |
Output is correct |
43 |
Incorrect |
900 ms |
1900 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1004 KB |
Output is correct |
2 |
Correct |
1 ms |
1004 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
1004 KB |
Output is correct |
5 |
Correct |
1 ms |
1004 KB |
Output is correct |
6 |
Correct |
1 ms |
1004 KB |
Output is correct |
7 |
Correct |
1 ms |
1004 KB |
Output is correct |
8 |
Correct |
1 ms |
1004 KB |
Output is correct |
9 |
Correct |
1 ms |
1004 KB |
Output is correct |
10 |
Correct |
2 ms |
1132 KB |
Output is correct |
11 |
Correct |
4 ms |
1388 KB |
Output is correct |
12 |
Correct |
13 ms |
1132 KB |
Output is correct |
13 |
Correct |
2 ms |
1132 KB |
Output is correct |
14 |
Correct |
58 ms |
1516 KB |
Output is correct |
15 |
Correct |
50 ms |
1516 KB |
Output is correct |
16 |
Correct |
2 ms |
1408 KB |
Output is correct |
17 |
Correct |
8 ms |
1900 KB |
Output is correct |
18 |
Correct |
2 ms |
1388 KB |
Output is correct |
19 |
Correct |
2 ms |
1388 KB |
Output is correct |
20 |
Correct |
3 ms |
1260 KB |
Output is correct |
21 |
Correct |
2 ms |
1260 KB |
Output is correct |
22 |
Correct |
2 ms |
1388 KB |
Output is correct |
23 |
Correct |
5 ms |
1388 KB |
Output is correct |
24 |
Correct |
9 ms |
1772 KB |
Output is correct |
25 |
Correct |
4 ms |
1644 KB |
Output is correct |
26 |
Correct |
3 ms |
1516 KB |
Output is correct |
27 |
Correct |
146 ms |
1516 KB |
Output is correct |
28 |
Correct |
24 ms |
2284 KB |
Output is correct |
29 |
Correct |
30 ms |
3700 KB |
Output is correct |
30 |
Correct |
7 ms |
1900 KB |
Output is correct |
31 |
Correct |
16 ms |
2924 KB |
Output is correct |
32 |
Correct |
11 ms |
2156 KB |
Output is correct |
33 |
Correct |
101 ms |
6404 KB |
Output is correct |
34 |
Correct |
90 ms |
6400 KB |
Output is correct |
35 |
Correct |
370 ms |
7676 KB |
Output is correct |
36 |
Correct |
9 ms |
2284 KB |
Output is correct |
37 |
Correct |
119 ms |
10888 KB |
Output is correct |
38 |
Correct |
128 ms |
10884 KB |
Output is correct |
39 |
Correct |
52 ms |
10500 KB |
Output is correct |
40 |
Correct |
86 ms |
10628 KB |
Output is correct |
41 |
Correct |
311 ms |
11344 KB |
Output is correct |
42 |
Correct |
7 ms |
1900 KB |
Output is correct |
43 |
Incorrect |
900 ms |
1900 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |