Submission #1223106

#TimeUsernameProblemLanguageResultExecution timeMemory
1223106AriadnaText editor (CEOI24_editor)C++20
45 / 100
1246 ms31920 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6;
int n, s1, s2, e1, e2;
int len[N];
map<pair<int, int>, int> dist;

void bfs(void) {
    priority_queue<pair<int, pair<int, int>>> q;
    dist[{s1, s2}] = 0;
    q.push({0, {s1, s2}});
    while (!q.empty()) {
        int d = -q.top().first;
        pair<int, int> u = q.top().second;
        int u1 = u.first, u2 = u.second;
        q.pop();
        if (d != dist[u]) continue;
        if (u1 == e1 && u2 == e2) return;

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

        for (pair<pair<int, int>, int> p: adj) {
            if (dist.find(p.first) == dist.end()) dist[p.first] = 1e18;
            if (dist[p.first] > dist[u]+p.second) {
                dist[p.first] = dist[u]+p.second;
                q.push({-dist[p.first], p.first});
            }
        }
    }
}

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

    }

    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...