Submission #1223084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223084		Ariadna	Text editor (CEOI24_editor)	C++20	14 / 100	761 ms	30736 KiB

Main

#include <bits/stdc++.h>
using namespace std;

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

void bfs(void) {
    priority_queue<pair<int, pair<int, int>>> q;
    dist[{s1, s2}] = 0;
    vis[s1][s2] = true;
    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});
        }
        // v
        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] = 1e9;
            if (dist[p.first] > dist[u]+p.second) {
                dist[p.first] = dist[u]+p.second;
                q.push({-dist[p.first], p.first});
            }
        }
    }
}

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;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44