Submission #1315825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315825		nguyenkhangninh99	Airplane (NOI23_airplane)	C++20	100 / 100	411 ms	25688 KiB

Main

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

const int maxn = 2e5 + 5, inf = 1e18 + 5;
vector<int> adj[maxn];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
      
    auto dijk = [&](int s) -> vector<int> {
       vector<int> d(n + 1, inf);
        d[s] = 0;
        priority_queue<pair<int, int>> pq; 
        pq.push({0, s});
        while(!pq.empty()){
            auto [dist, u] = pq.top(); 
            pq.pop();
            if(-dist != d[u]) continue;
            for(int v: adj[u]){
                int nxt = max(-dist + 1, a[v]);
                if(d[v] > nxt){
                    d[v] = nxt; 
                    pq.push({-d[v], v});
                }
            }
        }
        return d;
    };
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    vector<int> d1 = dijk(1), dn = dijk(n);
    int ans = inf;
    for(int u = 1; u <= n; u++){
        ans = min(ans, max(d1[u], dn[u]) * 2);
        for(int v: adj[u]){
            ans = min(ans, max(d1[u], dn[v]) * 2 + 1);
            ans = min(ans, max(d1[v], dn[u]) * 2 + 1);
        }
    }
    cout << ans;
}

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