Submission #1199922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199922		ofoz	Airplane (NOI23_airplane)	C++20	100 / 100	433 ms	31744 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define vi vector<int>
int n, m;
vi dijsktra(int source, vector<vi>& adj, vi& dist, vi& a) {
    vi height(n, 0);
    vector<int> mxHeight(n, 0);
    vector<bool> vis(n, false);
    set<ppi> s; // {{time spent, maximum altitude reached}, node}
    s.insert({{0, 0}, source});
    dist[source] = 0;
    while (!s.empty()) {
        pi p;
        int v, t, d;
        tie(p, v) = *s.begin();
        tie(t, d) = p;
        s.erase(s.begin());
        vis[v] = 1;
        for (int to : adj[v]) {
            if (vis[to]) continue;
            int to_time = t, to_height;
            if (d < a[to]) to_height = a[to];
            else to_height = d+1;
            to_time += max((a[to] - d), 1ll);

            if ((to_time > dist[to]) || (to_time == dist[to] && d < height[to])) continue;
            s.erase({{dist[to], height[to]}, to});
            dist[to] = to_time;
            height[to] = to_height;
            mxHeight[to] = max(mxHeight[to], max(a[to], d));
            s.insert({{dist[to], height[to]}, to});
        }
    }
    return mxHeight;
}

void solve() {
    cin >> n >> m;
    vector<vi> adj(n);
    vi a(n);
    for (int &x : a) cin >> x;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vi distSource(n, INT64_MAX);
    vi distEnd(n, INT64_MAX);
    vi heightS = dijsktra(0, adj, distSource, a);
    vi heightT = dijsktra(n-1, adj, distEnd, a);
    int res = INT64_MAX;
    for (int v = 0; v < n; v++) {
        int cur = distSource[v] + max(distEnd[v], heightS[v]);
        // cerr << v << ' ' << distSource[v] << ' ' << distEnd[v] << endl;
        if (heightS[v] < heightT[v]) continue;

        res = min(res, cur);
    }
    cout << res << endl;
}

// lets say we have a path from v to n-1.
// it can be seen that it will always be optimal to increase the height, and then at one given point start to decrease.

signed main() {
    solve();
    return 0;
}

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