#include <bits/stdc++.h>
using namespace std;
void subtask_1_2(int n) {
pair<int,int> start, end;
cin >> start.first >> start.second >> end.first >> end.second;
int l[n+1]; for (int i = 1; i <= n; i++) {
cin >> l[i];
l[i]++;
}
int dist[n+1][5002];
bool vis[n+1][5002] = {};
queue<pair<int,int>> q;
q.push(start);
vis[start.first][start.second] = true;
dist[start.first][start.second] = 0;
auto visit = [&](int to_x, int to_y, int from_x, int from_y) {
if (!vis[to_x][to_y]) {
dist[to_x][to_y] = dist[from_x][from_y] + 1;
vis[to_x][to_y] = true;
q.emplace(to_x, to_y);
}
};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
// left
if (x != 1 || y != 1) {
int l_x, l_y;
if (y == 1) {
l_x = x - 1;
l_y = l[x - 1];
} else {
l_x = x;
l_y = y - 1;
}
visit(l_x, l_y, x, y);
}
// right
if (x != n || y != 1) {
int r_x, r_y;
if (y == l[x]) {
r_x = x + 1;
r_y = 1;
} else {
r_x = x;
r_y = y + 1;
}
visit(r_x, r_y, x, y);
}
// up
if (x != 1) {
visit(x - 1, min(y, l[x - 1]), x, y);
}
// down
if (x != n) {
visit(x + 1, min(y, l[x + 1]), x, y);
}
}
cout << dist[end.first][end.second];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
if (n <= 1000) subtask_1_2(n);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
26 ms |
23644 KB |
Output is correct |
5 |
Correct |
26 ms |
20168 KB |
Output is correct |
6 |
Correct |
14 ms |
22108 KB |
Output is correct |
7 |
Correct |
30 ms |
23388 KB |
Output is correct |
8 |
Correct |
83 ms |
24972 KB |
Output is correct |
9 |
Correct |
59 ms |
20316 KB |
Output is correct |
10 |
Correct |
56 ms |
20824 KB |
Output is correct |
11 |
Correct |
55 ms |
20316 KB |
Output is correct |
12 |
Correct |
72 ms |
24972 KB |
Output is correct |
13 |
Correct |
67 ms |
24920 KB |
Output is correct |
14 |
Correct |
64 ms |
24920 KB |
Output is correct |
15 |
Correct |
55 ms |
24920 KB |
Output is correct |
16 |
Correct |
59 ms |
24924 KB |
Output is correct |
17 |
Correct |
62 ms |
24924 KB |
Output is correct |
18 |
Correct |
44 ms |
24920 KB |
Output is correct |
19 |
Correct |
34 ms |
24748 KB |
Output is correct |
20 |
Correct |
55 ms |
22364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |