Submission #1253314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253314		nasjes	Airplane (NOI23_airplane)	C++20	100 / 100	428 ms	45832 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m,k, t;
ll h[dim];


vll a[dim];
ll mn1[dim], mnn[dim];
void dey(ll st, ll *dst){
    dst[st]=0;
    set<pll> s;
    while(s.size()>0){
        ll v=(*s.begin()).se;
        for(auto x:a[v]){
            ll w=max<ll>(dst[v],h[x]);
            if(dst[x]>w){
                s.erase({ dst[x], x});
                dst[x]=w;
                s.insert({dst[x], x});
            }
        }
    }
}
int main() {

    ll  u,v, w, q, l, r;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>h[i];
        mn1[i]=inf;
        mnn[i]=inf;
    }
    for(int i=1; i<=m; i++){
        cin>>u>>v;
        a[u].pb(v);
        a[v].pb(u);
    }
    mn1[1]=0;
    set<pll> s;
    s.insert({0, 1});
    while(s.size()>0){
        ll v=(*s.begin()).se;
        s.erase(s.begin());
        for(auto x:a[v]){
            ll w=max<ll>(mn1[v]+1,h[x]);
            if(mn1[x]>w){
                s.erase({ mn1[x], x});
                mn1[x]=w;
                s.insert({mn1[x], x});
            }
        }
    }
    mnn[n]=0;
    s.insert({0, n});
    while(s.size()>0){
        ll v=(*s.begin()).se;
        s.erase(s.begin());
        for(auto x:a[v]){
            ll w=max<ll>(mnn[v]+1,h[x]);
            if(mnn[x]>w){
                s.erase({ mnn[x], x});
                mnn[x]=w;
                s.insert({mnn[x], x});
            }
        }
    }
/*    for(int i=1; i<=n; i++){
        cout<<mn1[i]<<" ";
    }
    cout<<endl;
    for(int i=1; i<=n; i++){
        cout<<mnn[i]<<" ";
    }*/
    ll ans=inf;
    for(int i=1; i<=n; i++){
        if(mn1[i]>=mnn[i])ans=min(ans, 2*mn1[i]);
        for(auto x: a[i]){
            if(mn1[i]>=mnn[x]){
                ans=min(ans, 2*mn1[i]+1);
            }
        }
    }
    cout<<ans<<endl;


    return 0;
}

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