Submission #873522

#	Time	Username	Problem	Language	Result	Execution time	Memory
873522		dsyz	Airplane (NOI23_airplane)	C++17	100 / 100	245 ms	31296 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	ll A[N];
	ll maxA = 0;
	for(ll i = 0;i < N;i++){
		cin>>A[i];
		maxA = max(maxA,A[i]);
	}
	vector<ll> v[N];
	for(ll i = 0;i < M;i++){
		ll a,b;
		cin>>a>>b;
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll start[N]; //either 0 or N - 1
	ll dist[N];
	memset(start,-1,sizeof(start));
	memset(dist,-1,sizeof(dist));
	dist[0] = 0;
	dist[N - 1] = 0;
	start[0] = 0;
	start[N - 1] = N - 1;
	pq.push({dist[0],0});
	pq.push({dist[N - 1],N - 1});
	while(!pq.empty()){
		ll x = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if(d != dist[x]){
			continue;
		}
		for(auto u : v[x]){
			if(dist[u] == -1 || dist[u] > max(A[u],dist[x] + 1)){
				dist[u] = max(A[u],dist[x] + 1);
				start[u] = start[x]; //started from node 0 or N - 1
				pq.push({dist[u],u});
			}
		}
	}
	ll ans = 1e18;
	for(ll x = 0;x < N;x++){
		for(auto u : v[x]){
			if(start[x] != start[u]){ 
				//one started from node 0, another one from node N - 1
				ll a = x;
				ll b = u;
				if(dist[a] > dist[b]) swap(a,b); //dist[a] is smaller
				ans = min(ans,dist[b] + max(A[b],dist[a] + 1));
			}
		}
	}
	cout<<ans<<'\n';
}

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