#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b); i > (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
/*
void file_in(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
*/
void normal()
{
ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
if (power == 0)
return 1;
ll result = ex(base, power / 2);
if (power % 2 == 1)
return(((result * result) % mod) * base) % mod;
else return (result * result) % mod;
}
const int maxn = 30005;
int dist[maxn], B[maxn], P[maxn];
vi powers[maxn];
int n, m;
void solve(int s)
{
priority_queue<pii, vector<pii>, greater<pii> > q;
q.push(mp(dist[s]=0, s));// first is distance, second is position
pii t;
while (!q.empty())
{
t = q.top(); q.pop();
if (t.f > dist[t.s]) continue;// we only need to find minimum distance, then if already greater than, no need to continue these values;
trav(p, powers[t.s])//powers
{
for (int x = 1;t.s + p * x < n;++x)
{
if (dist[t.s + p * x] > t.f + x)
{
q.push(mp(dist[t.s + p * x] = t.f + x, t.s + p * x));
if (binary_search(all(powers[t.s + p * x]), p)) break;//if there is a power there so no need to continue the other path
}
}
for (int x = 1;t.s - p * x >= 0;++x)//duplicate but -p instead of +p
{
if (dist[t.s - p * x] > t.f + x)//note that distance always increases
{
q.push(mp(dist[t.s - p * x] = t.f + x, t.s - p * x));
if (binary_search(all(powers[t.s - p * x]), p)) break;
}
}
}
}
}
int main()
{
normal();
cin >> n >> m;
set<int> temp;
FOR(i, 0, m)
{
cin >> B[i] >> P[i];
powers[B[i]].pb(P[i]);
}
FOR(i, 0, n)
{
sort(all(powers[i]));
powers[i].erase(unique(all(powers[i])), powers[i].end());//erase duplicates
}
fill(dist, dist + n, (int)1e9);
solve(B[0]);
if (dist[B[1]] == 1e9) cout << "-1";
else cout << dist[B[1]];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
1040 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
1 ms |
980 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
1 ms |
980 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
1 ms |
980 KB |
Output is correct |
17 |
Correct |
2 ms |
1108 KB |
Output is correct |
18 |
Correct |
1 ms |
980 KB |
Output is correct |
19 |
Correct |
1 ms |
980 KB |
Output is correct |
20 |
Correct |
3 ms |
1108 KB |
Output is correct |
21 |
Correct |
1 ms |
1068 KB |
Output is correct |
22 |
Correct |
1 ms |
980 KB |
Output is correct |
23 |
Correct |
2 ms |
980 KB |
Output is correct |
24 |
Correct |
1 ms |
1108 KB |
Output is correct |
25 |
Correct |
2 ms |
1128 KB |
Output is correct |
26 |
Correct |
1 ms |
980 KB |
Output is correct |
27 |
Correct |
1 ms |
980 KB |
Output is correct |
28 |
Correct |
1 ms |
1108 KB |
Output is correct |
29 |
Correct |
2 ms |
1236 KB |
Output is correct |
30 |
Correct |
1 ms |
1108 KB |
Output is correct |
31 |
Correct |
2 ms |
1108 KB |
Output is correct |
32 |
Correct |
1 ms |
1108 KB |
Output is correct |
33 |
Correct |
4 ms |
1368 KB |
Output is correct |
34 |
Correct |
4 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
1 ms |
980 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
1 ms |
980 KB |
Output is correct |
17 |
Correct |
1 ms |
1108 KB |
Output is correct |
18 |
Correct |
1 ms |
980 KB |
Output is correct |
19 |
Correct |
1 ms |
980 KB |
Output is correct |
20 |
Correct |
3 ms |
1108 KB |
Output is correct |
21 |
Correct |
1 ms |
980 KB |
Output is correct |
22 |
Correct |
1 ms |
980 KB |
Output is correct |
23 |
Correct |
1 ms |
980 KB |
Output is correct |
24 |
Correct |
1 ms |
1108 KB |
Output is correct |
25 |
Correct |
2 ms |
1108 KB |
Output is correct |
26 |
Correct |
1 ms |
980 KB |
Output is correct |
27 |
Correct |
1 ms |
980 KB |
Output is correct |
28 |
Correct |
1 ms |
1108 KB |
Output is correct |
29 |
Correct |
3 ms |
1236 KB |
Output is correct |
30 |
Correct |
1 ms |
1108 KB |
Output is correct |
31 |
Correct |
2 ms |
1108 KB |
Output is correct |
32 |
Correct |
1 ms |
1108 KB |
Output is correct |
33 |
Correct |
4 ms |
1368 KB |
Output is correct |
34 |
Correct |
4 ms |
1368 KB |
Output is correct |
35 |
Correct |
6 ms |
1492 KB |
Output is correct |
36 |
Correct |
2 ms |
1108 KB |
Output is correct |
37 |
Correct |
5 ms |
1492 KB |
Output is correct |
38 |
Correct |
8 ms |
1544 KB |
Output is correct |
39 |
Correct |
8 ms |
1600 KB |
Output is correct |
40 |
Correct |
7 ms |
1492 KB |
Output is correct |
41 |
Correct |
7 ms |
1492 KB |
Output is correct |
42 |
Correct |
5 ms |
1492 KB |
Output is correct |
43 |
Correct |
5 ms |
1492 KB |
Output is correct |
44 |
Correct |
6 ms |
1492 KB |
Output is correct |
45 |
Correct |
9 ms |
1748 KB |
Output is correct |
46 |
Correct |
9 ms |
1864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
980 KB |
Output is correct |
2 |
Correct |
1 ms |
980 KB |
Output is correct |
3 |
Correct |
1 ms |
980 KB |
Output is correct |
4 |
Correct |
1 ms |
980 KB |
Output is correct |
5 |
Correct |
1 ms |
980 KB |
Output is correct |
6 |
Correct |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Correct |
1 ms |
980 KB |
Output is correct |
11 |
Correct |
1 ms |
980 KB |
Output is correct |
12 |
Correct |
1 ms |
980 KB |
Output is correct |
13 |
Correct |
1 ms |
980 KB |
Output is correct |
14 |
Correct |
1 ms |
980 KB |
Output is correct |
15 |
Correct |
1 ms |
980 KB |
Output is correct |
16 |
Correct |
1 ms |
980 KB |
Output is correct |
17 |
Correct |
1 ms |
980 KB |
Output is correct |
18 |
Correct |
1 ms |
980 KB |
Output is correct |
19 |
Correct |
1 ms |
980 KB |
Output is correct |
20 |
Correct |
3 ms |
1108 KB |
Output is correct |
21 |
Correct |
1 ms |
980 KB |
Output is correct |
22 |
Correct |
1 ms |
980 KB |
Output is correct |
23 |
Correct |
1 ms |
980 KB |
Output is correct |
24 |
Correct |
2 ms |
1108 KB |
Output is correct |
25 |
Correct |
2 ms |
1108 KB |
Output is correct |
26 |
Correct |
1 ms |
980 KB |
Output is correct |
27 |
Correct |
1 ms |
980 KB |
Output is correct |
28 |
Correct |
1 ms |
1108 KB |
Output is correct |
29 |
Correct |
3 ms |
1184 KB |
Output is correct |
30 |
Correct |
1 ms |
1112 KB |
Output is correct |
31 |
Correct |
2 ms |
1108 KB |
Output is correct |
32 |
Correct |
1 ms |
1112 KB |
Output is correct |
33 |
Correct |
3 ms |
1368 KB |
Output is correct |
34 |
Correct |
4 ms |
1368 KB |
Output is correct |
35 |
Correct |
7 ms |
1492 KB |
Output is correct |
36 |
Correct |
2 ms |
1112 KB |
Output is correct |
37 |
Correct |
6 ms |
1496 KB |
Output is correct |
38 |
Correct |
9 ms |
1492 KB |
Output is correct |
39 |
Correct |
7 ms |
1500 KB |
Output is correct |
40 |
Correct |
8 ms |
1492 KB |
Output is correct |
41 |
Correct |
8 ms |
1488 KB |
Output is correct |
42 |
Correct |
5 ms |
1492 KB |
Output is correct |
43 |
Correct |
5 ms |
1492 KB |
Output is correct |
44 |
Correct |
7 ms |
1492 KB |
Output is correct |
45 |
Correct |
9 ms |
1876 KB |
Output is correct |
46 |
Correct |
9 ms |
1876 KB |
Output is correct |
47 |
Correct |
14 ms |
2392 KB |
Output is correct |
48 |
Correct |
6 ms |
1876 KB |
Output is correct |
49 |
Correct |
7 ms |
1976 KB |
Output is correct |
50 |
Correct |
5 ms |
1748 KB |
Output is correct |
51 |
Correct |
24 ms |
2956 KB |
Output is correct |
52 |
Correct |
24 ms |
2896 KB |
Output is correct |
53 |
Correct |
13 ms |
2892 KB |
Output is correct |
54 |
Correct |
2 ms |
1364 KB |
Output is correct |
55 |
Correct |
3 ms |
1364 KB |
Output is correct |
56 |
Correct |
397 ms |
2528 KB |
Output is correct |
57 |
Correct |
35 ms |
2380 KB |
Output is correct |
58 |
Correct |
7 ms |
1812 KB |
Output is correct |
59 |
Correct |
7 ms |
1936 KB |
Output is correct |
60 |
Correct |
7 ms |
1876 KB |
Output is correct |
61 |
Correct |
8 ms |
1944 KB |
Output is correct |
62 |
Correct |
10 ms |
2644 KB |
Output is correct |
63 |
Correct |
28 ms |
4048 KB |
Output is correct |
64 |
Correct |
31 ms |
3912 KB |
Output is correct |
65 |
Correct |
37 ms |
3924 KB |
Output is correct |
66 |
Correct |
80 ms |
5956 KB |
Output is correct |
67 |
Correct |
83 ms |
6084 KB |
Output is correct |