Submission #1222549

#TimeUsernameProblemLanguageResultExecution timeMemory
1222549AriadnaText editor (CEOI24_editor)C++20
14 / 100
346 ms24876 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int n, s1, s2, e1, e2;
int len[N];
int dist[1000][5001];
bool vis[1000][5001];

void bfs(void) {
    queue<pair<int, int>> q;
    dist[s1][s2] = 0;
    vis[s1][s2] = true;
    q.push({s1, s2});
    while (!q.empty()) {
        int u1 = q.front().first;
        int u2 = q.front().second;
        q.pop();
        vis[u1][u2] = true;
        if (u1 == e1 && u2 == e2) return;

        vector<pair<int, int>> adj;
        // <
        if (u2 > 0) {
            adj.push_back({u1, u2-1});
        } else if (u1 > 0) {
            adj.push_back({u1-1, len[u1-1]});
        }
        // >
        if (u2+1 <= len[u1]) {
            adj.push_back({u1, u2+1});
        } else if (u1+1 < n) {
            adj.push_back({u1+1, 0});
        }
        // ^
        if (u1 > 0) {
            if (u2 <= len[u1-1]) adj.push_back({u1-1, u2});
            else adj.push_back({u1-1, len[u1-1]});
        }
        // v
        if (u1+1 < n) {
            if (u2 <= len[u1+1]) adj.push_back({u1+1, u2});
            else adj.push_back({u1+1, len[u1+1]});
        }

        for (pair<int, int> p: adj) {
            if (!vis[p.first][p.second]) {
                dist[p.first][p.second] = dist[u1][u2]+1;
                q.push(p);
                vis[p.first][p.second] = true;
            }
        }
    }
}

int main() {
    cin >> n;
    cin >> s1 >> s2 >> e1 >> e2;
    --s1; --s2; --e1; --e2;
    for (int i = 0; i < n; ++i) cin >> len[i];
    bfs();
    cout << dist[e1][e2] << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...