Submission #1223474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223474		minhpk	Airplane (NOI23_airplane)	C++20	100 / 100	390 ms	44640 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int cnt[1000005];
int cnt1[1000005];
int bruh=1e16;
int height[1000005];
vector <int> z[1000005];

void dijkstra(){
     for (int i=1;i<=a;i++){
          cnt[i]=bruh;
     }

     priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>> > q;
     q.push({0,1});
     cnt[1]=0;
     while (q.size()){
         pair<int,int> pos= q.top();
         q.pop();
         int val=pos.first;
         int pos1=pos.second;

         if (val>cnt[pos1]){
             continue;
         }
         for (auto p:z[pos1]){
              if (cnt[p]>max(height[p],cnt[pos1]+1)){
                  cnt[p]=max(height[p],cnt[pos1]+1);
                  q.push({cnt[p],p});
              }
         }
     }
}

void dijkstra1(){
     for (int i=1;i<=a;i++){
          cnt1[i]=bruh;
     }

     priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>> > q;
     q.push({0,a});
     cnt1[a]=0;
     while (q.size()){
         pair<int,int> pos= q.top();
         q.pop();
         int val=pos.first;
         int pos1=pos.second;

         if (val>cnt1[pos1]){
             continue;
         }
         for (auto p:z[pos1]){
              if (cnt1[p]>max(height[p],val+1)){
                  cnt1[p]=max(height[p],val+1);
                  q.push({cnt1[p],p});
              }
         }
     }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> height[i];
    }
    for (int i=1;i<=b;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    dijkstra();
    dijkstra1();
    int min1=1e18;
    for (int i=1;i<=a;i++){
         min1=min(min1,2*max(cnt[i],cnt1[i]));
         for (auto p:z[i]){
              min1=min(min1,2*max(cnt[i],cnt1[p])+1);
         }
    }
    cout << min1 << "\n";

    return 0;
}

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