Submission #1164195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164195		veehj	Airplane (NOI23_airplane)	C++20	10 / 100	1101 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
//[NOISG 2023 Finals] Airplane
ll n, m, mxa;
vector<ll> a;
vector<vector<ll>> dp, adj;

bool chk(ll A, ll B){
  if(0<=A && A<n && 0<=B && B<mxa+2) return 1;
  return 0;
}

void f() {
  cin >> n >> m;
  a.resize(n);
  for(auto& u : a) cin >> u;
  mxa=*max_element(all(a));
  dp.assign(n, vector<ll>(mxa+2, -1));
  for(ll i=0; i<n; i++){
    for(ll j=0; j<a[i]; j++) dp[i][j]=-2;
  }
  adj.assign(n, vector<ll>(0));
  for(ll i=0; i<m; i++){
    ll x, y; cin >> x >> y;
    x--; y--;
    adj[x].pb(y);
    adj[y].pb(x);
  }
  priority_queue<pair<ll, pair<ll, ll>>> q;
  q.push({0, {0, 0}});
  while(!q.empty()){
    ll nw=q.top().fi*(-1);
    pair<ll, ll> plc=q.top().se;
    q.pop();
    if(dp[plc.fi][plc.se]!=-1 && dp[plc.fi][plc.se]<=nw) continue;
    dp[plc.fi][plc.se]=nw;
    vector<ll> dy={1, -1};
    for(int i=0; i<2; i++){
      if(chk(plc.fi, plc.se+dy[i])){
        if(dp[plc.fi][plc.se+dy[i]]==-2) continue;
        if(dp[plc.fi][plc.se+dy[i]]==-1 || dp[plc.fi][plc.se+dy[i]]>nw+1){
          q.push({(-1)*(nw+1), {plc.fi, plc.se+dy[i]}});
        }
      }
    }
    dy={-1, 0, 1};
    for(auto& u : adj[plc.fi]){
      for(int i=0; i<3; i++){
        if(chk(u, plc.se+dy[i])){
          if(dp[u][plc.se+dy[i]]==-2) continue;
          if(dp[u][plc.se+dy[i]]==-1 || dp[u][plc.se+dy[i]]>nw+1){
            q.push({(-1)*(nw+1), {u, plc.se+dy[i]}});
          }
        }
      }
    }
  }
  cout << dp[n-1][0];
}

int main() {
  int tc=1; 
  // cin >> tc;
  for(int i=1; i<=tc; i++){
    // cout << '#' << i << endl;
    f();
    if(i!=tc) cout << endl;
  }
}

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