Submission #1199904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199904		ofoz	Airplane (NOI23_airplane)	C++20	0 / 100	105 ms	19204 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<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 = max(d, a[to]);
            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;
            s.insert({{dist[to], height[to]}, to});
        }
    }
    return height;
}

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++) {
        // cerr << v+1 << ' ' << distSource[v] << ' ' << distEnd[v] << endl;
        res = min(res, distSource[v] + distEnd[v] + abs(heightS[v] - heightT[v]));
    }
    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: 0 / 22
• Subtask 2: 0 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37