#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 = 250;
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)
void djkistra(){
for(int i=0;i<N;i++){
mn[i] = inf;
for(int j=0;j<sq+10;j++)dist[i][j] = inf;
}
priority_queue<coisa> pq;
dist[b[0]][pwr(p[0])] =0;
mn[b[0]] = 0;
pq.push(coisa(dist[b[0]][pwr(p[0])],b[0],p[0]));
while(!pq.empty()){
coisa c = pq.top();
pq.pop();
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.push(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.push(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.push(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.push(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 |
Correct |
25 ms |
32384 KB |
Output is correct |
2 |
Correct |
24 ms |
32384 KB |
Output is correct |
3 |
Correct |
23 ms |
32384 KB |
Output is correct |
4 |
Correct |
25 ms |
32376 KB |
Output is correct |
5 |
Correct |
23 ms |
32504 KB |
Output is correct |
6 |
Correct |
24 ms |
32384 KB |
Output is correct |
7 |
Correct |
23 ms |
32384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
32384 KB |
Output is correct |
2 |
Correct |
23 ms |
32384 KB |
Output is correct |
3 |
Correct |
22 ms |
32376 KB |
Output is correct |
4 |
Correct |
22 ms |
32384 KB |
Output is correct |
5 |
Correct |
27 ms |
32376 KB |
Output is correct |
6 |
Correct |
24 ms |
32384 KB |
Output is correct |
7 |
Correct |
25 ms |
32384 KB |
Output is correct |
8 |
Correct |
22 ms |
32384 KB |
Output is correct |
9 |
Correct |
24 ms |
32512 KB |
Output is correct |
10 |
Correct |
23 ms |
32512 KB |
Output is correct |
11 |
Correct |
24 ms |
32640 KB |
Output is correct |
12 |
Correct |
23 ms |
32512 KB |
Output is correct |
13 |
Correct |
23 ms |
32384 KB |
Output is correct |
14 |
Correct |
25 ms |
32640 KB |
Output is correct |
15 |
Correct |
25 ms |
32640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
32384 KB |
Output is correct |
2 |
Correct |
23 ms |
32384 KB |
Output is correct |
3 |
Correct |
23 ms |
32384 KB |
Output is correct |
4 |
Correct |
25 ms |
32384 KB |
Output is correct |
5 |
Correct |
24 ms |
32384 KB |
Output is correct |
6 |
Correct |
22 ms |
32384 KB |
Output is correct |
7 |
Correct |
25 ms |
32384 KB |
Output is correct |
8 |
Correct |
25 ms |
32384 KB |
Output is correct |
9 |
Correct |
22 ms |
32512 KB |
Output is correct |
10 |
Correct |
23 ms |
32512 KB |
Output is correct |
11 |
Correct |
25 ms |
32640 KB |
Output is correct |
12 |
Correct |
23 ms |
32512 KB |
Output is correct |
13 |
Correct |
23 ms |
32512 KB |
Output is correct |
14 |
Correct |
24 ms |
32536 KB |
Output is correct |
15 |
Correct |
25 ms |
32640 KB |
Output is correct |
16 |
Correct |
25 ms |
32384 KB |
Output is correct |
17 |
Correct |
25 ms |
33280 KB |
Output is correct |
18 |
Correct |
23 ms |
32384 KB |
Output is correct |
19 |
Correct |
22 ms |
32512 KB |
Output is correct |
20 |
Correct |
24 ms |
34560 KB |
Output is correct |
21 |
Correct |
25 ms |
32384 KB |
Output is correct |
22 |
Correct |
25 ms |
32384 KB |
Output is correct |
23 |
Correct |
25 ms |
34176 KB |
Output is correct |
24 |
Correct |
29 ms |
34432 KB |
Output is correct |
25 |
Correct |
25 ms |
34560 KB |
Output is correct |
26 |
Correct |
26 ms |
34560 KB |
Output is correct |
27 |
Correct |
25 ms |
34560 KB |
Output is correct |
28 |
Correct |
26 ms |
34560 KB |
Output is correct |
29 |
Correct |
29 ms |
34560 KB |
Output is correct |
30 |
Correct |
26 ms |
34560 KB |
Output is correct |
31 |
Correct |
28 ms |
34560 KB |
Output is correct |
32 |
Correct |
27 ms |
34560 KB |
Output is correct |
33 |
Correct |
37 ms |
34560 KB |
Output is correct |
34 |
Correct |
36 ms |
34552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
32504 KB |
Output is correct |
2 |
Correct |
23 ms |
32384 KB |
Output is correct |
3 |
Correct |
25 ms |
32384 KB |
Output is correct |
4 |
Correct |
23 ms |
32376 KB |
Output is correct |
5 |
Correct |
23 ms |
32384 KB |
Output is correct |
6 |
Correct |
23 ms |
32384 KB |
Output is correct |
7 |
Correct |
22 ms |
32384 KB |
Output is correct |
8 |
Correct |
22 ms |
32384 KB |
Output is correct |
9 |
Correct |
22 ms |
32512 KB |
Output is correct |
10 |
Correct |
24 ms |
32640 KB |
Output is correct |
11 |
Correct |
23 ms |
32640 KB |
Output is correct |
12 |
Correct |
23 ms |
32512 KB |
Output is correct |
13 |
Correct |
23 ms |
32512 KB |
Output is correct |
14 |
Correct |
24 ms |
32640 KB |
Output is correct |
15 |
Correct |
24 ms |
32640 KB |
Output is correct |
16 |
Correct |
25 ms |
32384 KB |
Output is correct |
17 |
Correct |
29 ms |
33272 KB |
Output is correct |
18 |
Correct |
25 ms |
32384 KB |
Output is correct |
19 |
Correct |
25 ms |
32512 KB |
Output is correct |
20 |
Correct |
25 ms |
34560 KB |
Output is correct |
21 |
Correct |
22 ms |
32384 KB |
Output is correct |
22 |
Correct |
25 ms |
32384 KB |
Output is correct |
23 |
Correct |
24 ms |
34176 KB |
Output is correct |
24 |
Correct |
26 ms |
34432 KB |
Output is correct |
25 |
Correct |
24 ms |
34560 KB |
Output is correct |
26 |
Correct |
27 ms |
34560 KB |
Output is correct |
27 |
Correct |
29 ms |
34560 KB |
Output is correct |
28 |
Correct |
27 ms |
34560 KB |
Output is correct |
29 |
Correct |
32 ms |
34552 KB |
Output is correct |
30 |
Correct |
28 ms |
34560 KB |
Output is correct |
31 |
Correct |
30 ms |
34688 KB |
Output is correct |
32 |
Correct |
27 ms |
34560 KB |
Output is correct |
33 |
Correct |
35 ms |
34560 KB |
Output is correct |
34 |
Correct |
37 ms |
34556 KB |
Output is correct |
35 |
Correct |
38 ms |
34816 KB |
Output is correct |
36 |
Correct |
26 ms |
33664 KB |
Output is correct |
37 |
Correct |
44 ms |
35200 KB |
Output is correct |
38 |
Correct |
44 ms |
35320 KB |
Output is correct |
39 |
Correct |
45 ms |
35320 KB |
Output is correct |
40 |
Correct |
45 ms |
35320 KB |
Output is correct |
41 |
Correct |
44 ms |
35320 KB |
Output is correct |
42 |
Correct |
32 ms |
35104 KB |
Output is correct |
43 |
Correct |
29 ms |
35200 KB |
Output is correct |
44 |
Correct |
30 ms |
35200 KB |
Output is correct |
45 |
Correct |
84 ms |
35576 KB |
Output is correct |
46 |
Correct |
85 ms |
35572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
32384 KB |
Output is correct |
2 |
Correct |
25 ms |
32384 KB |
Output is correct |
3 |
Correct |
27 ms |
32384 KB |
Output is correct |
4 |
Correct |
25 ms |
32384 KB |
Output is correct |
5 |
Correct |
23 ms |
32384 KB |
Output is correct |
6 |
Correct |
22 ms |
32384 KB |
Output is correct |
7 |
Correct |
22 ms |
32384 KB |
Output is correct |
8 |
Correct |
25 ms |
32384 KB |
Output is correct |
9 |
Correct |
23 ms |
32512 KB |
Output is correct |
10 |
Correct |
22 ms |
32512 KB |
Output is correct |
11 |
Correct |
25 ms |
32640 KB |
Output is correct |
12 |
Correct |
23 ms |
32512 KB |
Output is correct |
13 |
Correct |
24 ms |
32512 KB |
Output is correct |
14 |
Correct |
26 ms |
32632 KB |
Output is correct |
15 |
Correct |
23 ms |
32640 KB |
Output is correct |
16 |
Correct |
22 ms |
32384 KB |
Output is correct |
17 |
Correct |
25 ms |
33280 KB |
Output is correct |
18 |
Correct |
23 ms |
32384 KB |
Output is correct |
19 |
Correct |
24 ms |
32472 KB |
Output is correct |
20 |
Correct |
26 ms |
34560 KB |
Output is correct |
21 |
Correct |
23 ms |
32384 KB |
Output is correct |
22 |
Correct |
23 ms |
32384 KB |
Output is correct |
23 |
Correct |
29 ms |
34176 KB |
Output is correct |
24 |
Correct |
28 ms |
34424 KB |
Output is correct |
25 |
Correct |
27 ms |
34560 KB |
Output is correct |
26 |
Correct |
29 ms |
34552 KB |
Output is correct |
27 |
Correct |
28 ms |
34560 KB |
Output is correct |
28 |
Correct |
29 ms |
34560 KB |
Output is correct |
29 |
Correct |
30 ms |
34552 KB |
Output is correct |
30 |
Correct |
26 ms |
34560 KB |
Output is correct |
31 |
Correct |
27 ms |
34560 KB |
Output is correct |
32 |
Correct |
28 ms |
34560 KB |
Output is correct |
33 |
Correct |
39 ms |
34552 KB |
Output is correct |
34 |
Correct |
37 ms |
34552 KB |
Output is correct |
35 |
Correct |
37 ms |
34684 KB |
Output is correct |
36 |
Correct |
26 ms |
33664 KB |
Output is correct |
37 |
Correct |
44 ms |
35200 KB |
Output is correct |
38 |
Correct |
44 ms |
35416 KB |
Output is correct |
39 |
Correct |
45 ms |
35392 KB |
Output is correct |
40 |
Correct |
45 ms |
35328 KB |
Output is correct |
41 |
Correct |
46 ms |
35448 KB |
Output is correct |
42 |
Correct |
33 ms |
35192 KB |
Output is correct |
43 |
Correct |
32 ms |
35200 KB |
Output is correct |
44 |
Correct |
30 ms |
35152 KB |
Output is correct |
45 |
Correct |
87 ms |
35576 KB |
Output is correct |
46 |
Correct |
83 ms |
35572 KB |
Output is correct |
47 |
Correct |
172 ms |
46324 KB |
Output is correct |
48 |
Correct |
31 ms |
33272 KB |
Output is correct |
49 |
Correct |
30 ms |
33272 KB |
Output is correct |
50 |
Correct |
28 ms |
33152 KB |
Output is correct |
51 |
Correct |
107 ms |
65268 KB |
Output is correct |
52 |
Correct |
124 ms |
65268 KB |
Output is correct |
53 |
Correct |
67 ms |
65016 KB |
Output is correct |
54 |
Correct |
44 ms |
64040 KB |
Output is correct |
55 |
Correct |
45 ms |
64120 KB |
Output is correct |
56 |
Correct |
56 ms |
65020 KB |
Output is correct |
57 |
Correct |
156 ms |
64508 KB |
Output is correct |
58 |
Correct |
58 ms |
64888 KB |
Output is correct |
59 |
Correct |
67 ms |
65016 KB |
Output is correct |
60 |
Correct |
77 ms |
65032 KB |
Output is correct |
61 |
Correct |
61 ms |
65016 KB |
Output is correct |
62 |
Correct |
115 ms |
65016 KB |
Output is correct |
63 |
Correct |
166 ms |
66184 KB |
Output is correct |
64 |
Correct |
269 ms |
66028 KB |
Output is correct |
65 |
Correct |
768 ms |
66292 KB |
Output is correct |
66 |
Execution timed out |
1088 ms |
65568 KB |
Time limit exceeded |
67 |
Halted |
0 ms |
0 KB |
- |