Submission #1214018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214018		VMaksimoski008	Airplane (NOI23_airplane)	C++17	100 / 100	371 ms	17516 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int N = 2e5 + 5;

vector<int> g[N];
int n, m, a[N], D[N][2], ans = 1e9;

void sp(int s, int t) {
    for(int i=1; i<=n; i++) D[i][t] = 1e9;
    priority_queue<pii, vector<pii>, greater<> > pq;
    pq.push({ D[s][t] = 0, s });

    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d != D[u][t]) continue;

        for(int v : g[u]) {
            int w = max(d + 1, a[v]);
            if(D[v][t] > w) pq.push({ D[v][t] = w, v });
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];

    while(m--) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    sp(1, 0);
    sp(n, 1);

    for(int u=1; u<=n; u++) {
        ans = min(ans, 2 * max(D[u][0], D[u][1]));
        for(int v : g[u])
            for(int i : { 0, 1 })
                ans = min(ans, 2 * max(D[u][i], D[v][i^1]) + 1);
    }

    cout << ans;
}

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