#include <bits/stdc++.h>
using namespace std;
/*
we run dijkstra
let B = 100
for all doges that have p >= b, just simulate the jumps
how do we deal with the "small" doges??
note that the answer is never more than 30000...
*/
const int SMALL = 100;
const int MAXN = 30000;
const int INF = 1e9;
int mintime[MAXN][SMALL + 1];
int dist[MAXN];
vector<int> doges[MAXN];
bitset<MAXN> todo[MAXN + 1];
int main() {
int n; cin >> n;
int m; cin >> m;
for (int i = 0; i < n; i ++)
for (int j = 1; j <= SMALL; j ++)
mintime[i][j] = INF;
for (int i = 0; i < n; i ++)
dist[i] = INF;
int startnode = -1, target = -1;
for (int i = 0; i < m; i ++) {
int b, p; cin >> b >> p;
if (i == 0)
startnode = b;
else if (i == 1)
target = b;
doges[b].push_back(p);
}
if (startnode == target) {
cout << 0 << endl; return 0;
}
todo[0][startnode] = 1;
dist[0] = 0;
bool done = false;
for (int t = 0; t <= n; t ++) {
while (true) {
int xx = todo[t]._Find_first();
if (xx == MAXN) break;
todo[t][xx] = false;
int curnode = xx;
for (auto doge : doges[curnode]) {
// big doge
if (doge > SMALL) {
int extratime = 0;
for (int j = curnode - doge; j >= 0; j -= doge) {
extratime ++;
if (dist[j] > extratime + t) {
if (dist[j] != INF)
todo[dist[j]][j] = 0;
dist[j] = extratime + t;
todo[dist[j]][j] = 1;
}
}
extratime = 0;
for (int j = curnode + doge; j < n; j += doge) {
extratime ++;
if (dist[j] > extratime + t) {
if (dist[j] != INF)
todo[dist[j]][j] = 0;
dist[j] = extratime + t;
todo[dist[j]][j] = 1;
}
}
}
// small doge
else {
// ignore entirely
if (mintime[curnode][doge] <= t)
continue;
mintime[curnode][doge] = t;
int extratime = 0;
for (int j = curnode - doge; j >= 0; j -= doge) {
extratime ++;
// stop
if (mintime[j][doge] <= t + extratime)
break;
mintime[j][doge] = t + extratime;
if (dist[j] > extratime + t) {
if (dist[j] != INF)
todo[dist[j]][j] = 0;
dist[j] = extratime + t;
todo[dist[j]][j] = 1;
}
}
extratime = 0;
for (int j = curnode + doge; j < n; j += doge) {
extratime ++;
// stop
if (mintime[j][doge] <= t + extratime)
break;
mintime[j][doge] = t + extratime;
if (dist[j] > extratime + t) {
if (dist[j] != INF)
todo[dist[j]][j] = 0;
dist[j] = extratime + t;
todo[dist[j]][j] = 1;
}
}
}
}
if (curnode == target) {
done = true; break;
}
}
if (done) break;
}
if (dist[target] == INF) {
cout << -1 << endl;
} else cout << dist[target] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2496 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
6584 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2652 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1372 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
