#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int B[30000], P[30000];
vector<int> A[30000];
int vis[2000][30001];
int main() {
int N, M; cin >> N >> M;
for(int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
A[B[i]].push_back(i);
}
int ans = -1;
deque<pair<int, int> > Q;
Q.push_back({B[0], M});
vis[B[0]][M] = 1;
while(!Q.empty()) {
auto it = Q.front(); Q.pop_front();
int i = it.first, j = it.second;
if(i == B[1]) {
ans = vis[i][j];
break;
}
if(j == M) {
for(int k: A[i]) {
if(!vis[i][k]) {
vis[i][k] = vis[i][j];
Q.push_front({i, k});
}
}
}
else {
if(i - P[j] >= 0 && !vis[i - P[j]][j]) {
vis[i - P[j]][j] = vis[i][j] + 1;
Q.push_back({i - P[j], j});
}
if(i + P[j] < N && !vis[i + P[j]][j]) {
vis[i + P[j]][j] = vis[i][j] + 1;
Q.push_back({i + P[j], j});
}
if(!vis[i][M]) {
vis[i][M] = vis[i][j];
Q.push_front({i, M});
}
}
}
cout << ans - 1 << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
237340 KB |
Output is correct |
2 |
Correct |
0 ms |
237340 KB |
Output is correct |
3 |
Correct |
0 ms |
237340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
237340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
237340 KB |
Output is correct |
2 |
Correct |
0 ms |
237340 KB |
Output is correct |
3 |
Correct |
0 ms |
237340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
237340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
237340 KB |
Output is correct |
2 |
Correct |
0 ms |
237340 KB |
Output is correct |
3 |
Correct |
0 ms |
237340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
237340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
237340 KB |
Output is correct |
2 |
Correct |
0 ms |
237340 KB |
Output is correct |
3 |
Correct |
0 ms |
237340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
237340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
237340 KB |
Output is correct |
2 |
Correct |
0 ms |
237340 KB |
Output is correct |
3 |
Correct |
0 ms |
237340 KB |
Output is correct |
4 |
Incorrect |
0 ms |
237340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |