#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 = 3e4 + 10;
int b[N],p[N];
const int sq = 2;
int mark[N];
int dist[N][sq + 3];
vi aqui[N];
int mn[N];
const int inf = 1e9;
int rev[N];
vector<pii> pq[N*sq];
#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+2;j++)dist[i][j] = inf;
}
dist[b[0]][pwr(p[0])] =0;
mn[b[0]] = 0;
pq[0].pb(pii(b[0],0));
for(int D=0;!pq[D].empty();D++){
while(!pq[D].empty()){
pii c = pq[D].back();
pq[D].pop_back();
int d = D;
int cur = c.ff;
if(mn[cur] > d)mn[cur] = d;
if(p[c.ss] <= sq){
aqui[cur].pb(c.ss);
}
for(int id : aqui[cur]){
int x = p[id];
if(x > sq){
if(dist[cur][sq+1]==inf)dist[cur][sq+1] = d;
if(mark[id])continue;
mark[id] = 1;
int t=0;
for(int l = cur-x;l>=0;l-=x){
t++;
pq[d+t].pb(pii(l,id));
}
t=0;
for(int l = cur + x;l<n;l+=x){
t++;
pq[d+t].pb(pii(l,id));
}
}else{
dist[cur][x] = min(dist[cur][x],d);
if(cur - x >=0 and dist[cur-x][x] == inf){
dist[cur-x][x] = d + 1;
pq[d+1].pb(pii(cur - x,id));
}
if(cur + x < n and dist[cur + x][x] == inf){
dist[cur + x][x] = d + 1;
pq[d+1].pb(pii(cur + x,id));
}
}
}
aqui[cur].clear();
}
}
int res = mn[b[1]];
for(int i=1;i<=sq+1;i++)res = min(res,dist[b[1]][i]);
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(i);
}
djkistra();
// Math -> gcd it all
// Did u check N=1? Did you switch N,M?
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3200 KB |
Output is correct |
2 |
Correct |
7 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
6 ms |
3200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3200 KB |
Output is correct |
2 |
Correct |
6 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
7 ms |
3200 KB |
Output is correct |
8 |
Correct |
6 ms |
3072 KB |
Output is correct |
9 |
Correct |
7 ms |
3200 KB |
Output is correct |
10 |
Correct |
6 ms |
3200 KB |
Output is correct |
11 |
Correct |
8 ms |
3328 KB |
Output is correct |
12 |
Correct |
7 ms |
3232 KB |
Output is correct |
13 |
Correct |
7 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
15 |
Correct |
6 ms |
3200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3200 KB |
Output is correct |
2 |
Correct |
6 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
6 ms |
3200 KB |
Output is correct |
8 |
Correct |
6 ms |
3200 KB |
Output is correct |
9 |
Correct |
7 ms |
3200 KB |
Output is correct |
10 |
Correct |
7 ms |
3200 KB |
Output is correct |
11 |
Correct |
7 ms |
3328 KB |
Output is correct |
12 |
Correct |
7 ms |
3200 KB |
Output is correct |
13 |
Correct |
6 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
15 |
Correct |
6 ms |
3200 KB |
Output is correct |
16 |
Correct |
7 ms |
3200 KB |
Output is correct |
17 |
Correct |
7 ms |
3328 KB |
Output is correct |
18 |
Correct |
7 ms |
3200 KB |
Output is correct |
19 |
Correct |
6 ms |
3200 KB |
Output is correct |
20 |
Correct |
7 ms |
3328 KB |
Output is correct |
21 |
Correct |
8 ms |
3200 KB |
Output is correct |
22 |
Correct |
6 ms |
3200 KB |
Output is correct |
23 |
Correct |
7 ms |
3328 KB |
Output is correct |
24 |
Correct |
7 ms |
3328 KB |
Output is correct |
25 |
Correct |
7 ms |
3328 KB |
Output is correct |
26 |
Correct |
7 ms |
3456 KB |
Output is correct |
27 |
Correct |
7 ms |
3456 KB |
Output is correct |
28 |
Correct |
8 ms |
3840 KB |
Output is correct |
29 |
Correct |
8 ms |
3968 KB |
Output is correct |
30 |
Correct |
7 ms |
3456 KB |
Output is correct |
31 |
Correct |
8 ms |
3712 KB |
Output is correct |
32 |
Correct |
7 ms |
3456 KB |
Output is correct |
33 |
Correct |
11 ms |
4480 KB |
Output is correct |
34 |
Correct |
11 ms |
4352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3200 KB |
Output is correct |
2 |
Correct |
6 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
7 ms |
3328 KB |
Output is correct |
7 |
Correct |
7 ms |
3200 KB |
Output is correct |
8 |
Correct |
6 ms |
3200 KB |
Output is correct |
9 |
Correct |
6 ms |
3200 KB |
Output is correct |
10 |
Correct |
6 ms |
3200 KB |
Output is correct |
11 |
Correct |
7 ms |
3328 KB |
Output is correct |
12 |
Correct |
7 ms |
3200 KB |
Output is correct |
13 |
Correct |
6 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
15 |
Correct |
7 ms |
3200 KB |
Output is correct |
16 |
Correct |
6 ms |
3200 KB |
Output is correct |
17 |
Correct |
7 ms |
3456 KB |
Output is correct |
18 |
Correct |
6 ms |
3200 KB |
Output is correct |
19 |
Correct |
7 ms |
3200 KB |
Output is correct |
20 |
Correct |
7 ms |
3328 KB |
Output is correct |
21 |
Correct |
7 ms |
3200 KB |
Output is correct |
22 |
Correct |
6 ms |
3200 KB |
Output is correct |
23 |
Correct |
7 ms |
3328 KB |
Output is correct |
24 |
Correct |
7 ms |
3328 KB |
Output is correct |
25 |
Correct |
9 ms |
3328 KB |
Output is correct |
26 |
Correct |
7 ms |
3456 KB |
Output is correct |
27 |
Correct |
7 ms |
3456 KB |
Output is correct |
28 |
Correct |
8 ms |
3968 KB |
Output is correct |
29 |
Correct |
8 ms |
3968 KB |
Output is correct |
30 |
Correct |
8 ms |
3456 KB |
Output is correct |
31 |
Correct |
8 ms |
3712 KB |
Output is correct |
32 |
Correct |
7 ms |
3584 KB |
Output is correct |
33 |
Correct |
10 ms |
4480 KB |
Output is correct |
34 |
Correct |
10 ms |
4352 KB |
Output is correct |
35 |
Correct |
18 ms |
4864 KB |
Output is correct |
36 |
Correct |
8 ms |
3456 KB |
Output is correct |
37 |
Correct |
18 ms |
6012 KB |
Output is correct |
38 |
Correct |
19 ms |
5756 KB |
Output is correct |
39 |
Correct |
19 ms |
5888 KB |
Output is correct |
40 |
Correct |
19 ms |
5884 KB |
Output is correct |
41 |
Correct |
19 ms |
5756 KB |
Output is correct |
42 |
Correct |
11 ms |
3968 KB |
Output is correct |
43 |
Correct |
12 ms |
3968 KB |
Output is correct |
44 |
Correct |
11 ms |
3840 KB |
Output is correct |
45 |
Correct |
27 ms |
7916 KB |
Output is correct |
46 |
Correct |
27 ms |
8040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3200 KB |
Output is correct |
2 |
Correct |
6 ms |
3200 KB |
Output is correct |
3 |
Correct |
6 ms |
3200 KB |
Output is correct |
4 |
Correct |
6 ms |
3200 KB |
Output is correct |
5 |
Correct |
6 ms |
3200 KB |
Output is correct |
6 |
Correct |
6 ms |
3200 KB |
Output is correct |
7 |
Correct |
7 ms |
3200 KB |
Output is correct |
8 |
Correct |
6 ms |
3200 KB |
Output is correct |
9 |
Correct |
6 ms |
3200 KB |
Output is correct |
10 |
Correct |
6 ms |
3200 KB |
Output is correct |
11 |
Correct |
7 ms |
3328 KB |
Output is correct |
12 |
Correct |
6 ms |
3200 KB |
Output is correct |
13 |
Correct |
6 ms |
3200 KB |
Output is correct |
14 |
Correct |
7 ms |
3200 KB |
Output is correct |
15 |
Correct |
6 ms |
3200 KB |
Output is correct |
16 |
Correct |
6 ms |
3200 KB |
Output is correct |
17 |
Correct |
7 ms |
3456 KB |
Output is correct |
18 |
Correct |
6 ms |
3200 KB |
Output is correct |
19 |
Correct |
6 ms |
3200 KB |
Output is correct |
20 |
Correct |
7 ms |
3328 KB |
Output is correct |
21 |
Correct |
6 ms |
3200 KB |
Output is correct |
22 |
Correct |
6 ms |
3200 KB |
Output is correct |
23 |
Correct |
7 ms |
3328 KB |
Output is correct |
24 |
Correct |
7 ms |
3328 KB |
Output is correct |
25 |
Correct |
7 ms |
3328 KB |
Output is correct |
26 |
Correct |
7 ms |
3456 KB |
Output is correct |
27 |
Correct |
7 ms |
3456 KB |
Output is correct |
28 |
Correct |
8 ms |
3840 KB |
Output is correct |
29 |
Correct |
9 ms |
3968 KB |
Output is correct |
30 |
Correct |
8 ms |
3456 KB |
Output is correct |
31 |
Correct |
7 ms |
3712 KB |
Output is correct |
32 |
Correct |
7 ms |
3584 KB |
Output is correct |
33 |
Correct |
11 ms |
4352 KB |
Output is correct |
34 |
Correct |
10 ms |
4352 KB |
Output is correct |
35 |
Correct |
15 ms |
4864 KB |
Output is correct |
36 |
Correct |
8 ms |
3456 KB |
Output is correct |
37 |
Correct |
18 ms |
6012 KB |
Output is correct |
38 |
Correct |
20 ms |
5756 KB |
Output is correct |
39 |
Correct |
18 ms |
5888 KB |
Output is correct |
40 |
Correct |
19 ms |
5884 KB |
Output is correct |
41 |
Correct |
18 ms |
5756 KB |
Output is correct |
42 |
Correct |
12 ms |
3968 KB |
Output is correct |
43 |
Correct |
12 ms |
3968 KB |
Output is correct |
44 |
Correct |
11 ms |
3840 KB |
Output is correct |
45 |
Correct |
25 ms |
7916 KB |
Output is correct |
46 |
Correct |
25 ms |
7912 KB |
Output is correct |
47 |
Correct |
43 ms |
12636 KB |
Output is correct |
48 |
Correct |
13 ms |
4096 KB |
Output is correct |
49 |
Correct |
12 ms |
3968 KB |
Output is correct |
50 |
Correct |
11 ms |
3840 KB |
Output is correct |
51 |
Correct |
30 ms |
8440 KB |
Output is correct |
52 |
Correct |
40 ms |
8312 KB |
Output is correct |
53 |
Correct |
24 ms |
6016 KB |
Output is correct |
54 |
Correct |
8 ms |
4096 KB |
Output is correct |
55 |
Correct |
10 ms |
4480 KB |
Output is correct |
56 |
Correct |
19 ms |
5504 KB |
Output is correct |
57 |
Correct |
216 ms |
63736 KB |
Output is correct |
58 |
Correct |
17 ms |
6528 KB |
Output is correct |
59 |
Runtime error |
27 ms |
13568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
60 |
Halted |
0 ms |
0 KB |
- |