Submission #1184854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184854		SalihSahin	Airplane (NOI23_airplane)	C++20	100 / 100	200 ms	25336 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define pb push_back
using namespace std;

const int inf = 1e9*2;
const int N = 2e5 + 20;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin>>n>>m;
    vector<int> adj[n], a(n);
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    for(int i = 0; i < m; i++){
        int u, v;
        cin>>u>>v;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vector<int> dis1(n, inf), vis(n);
    dis1[0] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({0, 0});
    while(!pq.empty()){
        int node = pq.top().second;
        pq.pop();

        if(vis[node]) continue;
        vis[node] = 1;

        for(auto itr: adj[node]){
            if(dis1[itr] > max(dis1[node] + 1, a[itr])){
                dis1[itr] = max(dis1[node] + 1, a[itr]);
                pq.push({-dis1[itr], itr});
            }
        }
    }

    vector<int> disn(n, inf);
    for(int i = 0; i < n; i++){
        vis[i] = 0;
    }
    disn[n-1] = 0;
    pq.push({0, n-1});
    while(!pq.empty()){
        int node = pq.top().second;
        pq.pop();

        if(vis[node]) continue;
        vis[node] = 1;

        for(auto itr: adj[node]){
            if(disn[itr] > max(disn[node] + 1, a[itr])){
                disn[itr] = max(disn[node] + 1, a[itr]);
                pq.push({-disn[itr], itr});
            }
        }
    }

    int ans = inf;
    if(dis1[n-1] == 1){
        cout<<1<<endl;
        return 0;
    }
    for(int i = 0; i < n; i++){
        ans = min(ans, max(dis1[i], disn[i]) * 2);
    }
    for(int i = 0; i < n; i++){
        for(auto itr: adj[i]){
            int val = max(dis1[i], disn[itr]) * 2 + 1;
            ans = min(ans, val);
        }
    }

    cout<<ans<<endl;
    return 0;
}

/*
11 12
0 0 0 0 0 0 2 2 1 5 0
1 2
2 3
3 4
4 5
5 6
6 11
1 7
7 8
8 9
9 11
1 10
10 11
*/

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