Submission #1171540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171540		ackhava	Airplane (NOI23_airplane)	C++20	100 / 100	980 ms	42520 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define REP(v, i, j) for (int v = i; v != j; v++)
#define FORI(v) for (auto i : v)
#define FORJ(v) for (auto j : v)

#define OUT(v, a) \
    FORI(v)       \
    cout << i << a;
#define OUTS(v, a, b)      \
    cout << v.size() << a; \
    OUT(v, b)
#define in(a, n) \
    REP(i, 0, n) \
    cin >> a[i];

#define SORT(v) sort(begin(v), end(v))
#define REV(v) reverse(begin(v), end(v))
#define MEMSET(m) memset(m, -1, sizeof m)

#define pb push_back
#define fi first
#define se second

#define detachIO                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
    
using namespace std;

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
    if(__x.size() != __y.size()) return false;
    return std::equal(__x.begin(), __x.end(), __y.begin());
}


typedef pair<long long, long long> pii;
typedef pair<pii, long long> piii;
typedef pair<pii, pii> piiii;

int d1[200100];
int d2[200100];
int o1[200100];
int o2[200100];

vector<int> adj[200100];
int h[200100];

signed main(){
    int n;cin>>n;
    int m;cin>>m;
    REP(i,0,n){
        cin>>h[i];
    }
    REP(i,0,n+20)d1[i]=2e18,d2[i]=2e18;
    REP(i,0,m){
        int x,y;cin>>x>>y;x--,y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    set<int> vis;
    pq.push({0,0});
    while(pq.size()){
        auto top=pq.top();
        pq.pop();
        if(vis.count(top.se))continue;
        vis.insert(top.se);
        if(top.fi>d1[top.se])continue;
        d1[top.se]=top.fi;
        o1[top.se]=max(o1[top.se],h[top.se]);
        FORI(adj[top.se]){
            int t=max(top.fi+1,h[i]);
            if(d1[i]>t)d1[i]=t,o1[i]=max(o1[top.se],h[i]);
            if(d1[i]==t)d1[i]=t,o1[i]=min(o1[i],max(o1[top.se],h[i]));
            pq.push({t,i});
        }
    }
    pq.push({0,n-1});
    vis.clear();
    while(pq.size()){
        auto top=pq.top();
        pq.pop();
        if(vis.count(top.se))continue;
        vis.insert(top.se);
        if(top.fi>d2[top.se])continue;
        d2[top.se]=top.fi;
        o2[top.se]=max(o2[top.se],h[top.se]);
        FORI(adj[top.se]){
            int t=max(top.fi+1,h[i]);
            if(d2[i]>t)d2[i]=t,o2[i]=max(o2[top.se],h[i]);
            if(d2[i]==t)d2[i]=t,o2[i]=min(o2[i],max(o2[top.se],h[i]));
            pq.push({t,i});
        }
    }
    int ans=3e18;
    REP(i,0,n){
        if(o1[i]==h[i] && o2[i]==h[i])ans=min(ans,d1[i]+d2[i]);
    }
    // REP(i,0,n)cerr<<o1[i]<<" ";
    // cerr<<endl;
    // REP(i,0,n)cerr<<h[i]<<" ";
    // cerr<<endl;
    // REP(i,0,n)cerr<<o2[i]<<" ";
    // cerr<<endl;
    // REP(i,0,n)cerr<<d1[i]<<" ";
    // cerr<<endl;
    // REP(i,0,n)cerr<<d2[i]<<" ";
    // cerr<<endl;
    cout<<ans<<'\n';
}

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