Submission #886971

#	Time	Username	Problem	Language	Result	Execution time	Memory
886971		efedmrlr	Airplane (NOI23_airplane)	C++17	100 / 100	265 ms	24228 KiB

Main

#include <bits/stdc++.h>

#define lli long long int
#define MP make_pair
#define REP(i,n) for(int i = 0; (i)<(n); (i)++)
#define pb push_back

const int N = 2e5+5;
const int M = 4e3+5;
const int MOD = 1e9+7;
const int INF = 1e9 + 500;
using namespace std;

void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}
int n,m,q;
vector<int> a(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<int> dp1, dp2;
void bfs(int src, vector<int> &sp) {
    priority_queue<array<int,2>, vector<array<int,2> >, greater<array<int,2> > > que;
    sp.assign(n + 3, INF);
    sp[src] = 0;
    que.push({0, src});
    while(que.size()) {
        auto cur = que.top();
        que.pop();
        for(auto c : adj[cur[1]]) {
            if(sp[c] != INF) continue;

            sp[c] = max(cur[0] + 1 , a[c]);
            que.push({sp[c], c});
        }
    } 

}


void solve() {
    cin>>n>>m;
    REP(i,n) cin>>a[i + 1];
    for(int i = 1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int ans = INF;
    bfs(1, dp1);
    bfs(n, dp2);
    for(int i = 1; i<=n; i++) {
        int ret = max(dp1[i] , dp2[i]) * 2;
        ans = min(ans , ret);
    }
    for(int i = 1; i<=n; i++) {
        for(auto c : adj[i]) {
            if(dp1[i] == dp2[c]) ans = min(ans, dp1[i] * 2 + 1);  
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    fastio();
    solve();
}   

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