Submission #1223106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223106		Ariadna	Text editor (CEOI24_editor)	C++20	45 / 100	1246 ms	31920 KiB

Main

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

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