Submission #1271804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271804		altern23	Airplane (NOI23_airplane)	C++20	0 / 100	52 ms	15944 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 4e18;
const int MOD = 998244353;

ll dp_L[MAXN + 5], dp_R[MAXN + 5];
ll A[MAXN + 5];

vector<ll> adj[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M; cin >> N >> M;
		
		for(int i = 1; i <= N; i++){
			cin >> A[i];
			dp_L[i] = dp_R[i] = INF;
		}
		
		for(int i = 1; i <= M; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		
		priority_queue<pii> pq;
		pq.push({0, 1});
		
		for(;!pq.empty();){
			auto [val, idx] = pq.top(); pq.pop();
			val = -val;
			for(auto i : adj[idx]){
				if(dp_L[i] > max(val + 1, A[i])){
					dp_L[i] = max(val + 1, A[i]);
					pq.push({-dp_L[i], i});
				}
			}
		}
		
		pq.push({0, N});
		
		for(;!pq.empty();){
			auto [val, idx] = pq.top(); pq.pop();
			val = -val;
			for(auto i : adj[idx]){
				if(dp_R[i] > max(val + 1, A[i])){
					dp_R[i] = max(val + 1, A[i]);
					pq.push({-dp_R[i], i});
				}
			}
		}
		
		ll ans = INF;
		for(int i = 1; i <= N; i++){
			for(auto j : adj[i]){
				ll MX = max(dp_L[i], dp_R[j]);
				ans = min(ans, MX * 2 + 1);
			}
			ans = min(ans, max(dp_L[i], dp_R[i]) * 2);
		}
		
		cout << ans << "\n";
	}
}

/*

*/

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