Submission #1099216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099216		NoMercy	Airplane (NOI23_airplane)	C++17	32 / 100	1029 ms	19560 KiB

Main

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

typedef long long ll;
 
const ll inf = 1e18;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, M;
    cin >> N >> M;
    vector<int> h(N), g[N];
    vector<array<ll, 2>> dist(N);
    for (int i = 0;i < N;i ++) {
        cin >> h[i];
    }
    for (int i = 0;i < M;i ++) {
        int u, v; 
        cin >> u >> v;
        -- u;
        -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    function<void(int, int)> dijikstra = [&](int si, int ti) -> void {
        for (int i = 0;i < N;i ++) {
            dist[i][ti] = inf;
        }
        dist[si][ti] = 0;
        multiset<array<ll, 2>> dj;
        dj.insert({dist[si][ti], si});
        while (dj.size() > 0) {
            auto [w, u] = *dj.begin();
            dj.erase(dj.begin());
            w = -w;
            if (w != dist[u][ti]) continue;
            for (auto v : g[u]) if (dist[v][ti] > max(1LL * h[v], dist[u][ti] + 1)) {
                dist[v][ti] = max(1LL * h[v], dist[u][ti] + 1);
                dj.insert({-dist[v][ti], v});
            }
        }
    };
    dijikstra(0, 0);
    dijikstra(N - 1, 1);

    ll ans = inf;
    for (int u = 0;u < N;u ++) {
        ans = min(ans, max(dist[u][0], dist[u][1]) * 2);
        for (auto v : g[u]) {
            ans = min(ans, max(dist[v][0], dist[u][1]) * 2 + 1);
            ans = min(ans, max(dist[u][0], dist[v][1]) * 2 + 1);
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37