Submission #891931

#	Time	Username	Problem	Language	Result	Execution time	Memory
891931		vjudge1	Airplane (NOI23_airplane)	C++17	100 / 100	212 ms	20524 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,m;
int step[MAX],fx[MAX];
vector<int> adj[MAX];
int a[MAX];

priority_queue<ii,vector<ii>,greater<ii>> pq;

signed main(){
	
	read();
	
	cin >> n >> m;
	
	for(int i = 1;i <= n;i++)cin >> a[i];
	
	for(int i = 1,u,v;i <= m;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	memset(step,0x3f,sizeof step);
	memset(fx,0x3f,sizeof fx);
	
	pq.push({0,1});
	step[1] = 0;
	
	while(!pq.empty()){
		int u = pq.top().Y;
		int d = pq.top().X;
		
		pq.pop();
		
		if(d != step[u])continue;
		
		for(auto v : adj[u]){
			if(step[v] > max(step[u] + 1,a[v])){
				step[v] = max(step[u] + 1,a[v]);
				pq.push({step[v],v});
			}
		}
	}
	
	pq.push({0,n});
	fx[n] = 0;
	
	while(!pq.empty()){
		int u = pq.top().Y;
		int d = pq.top().X;
		
		pq.pop();
		
		if(d != fx[u])continue;
		
		for(auto v : adj[u]){
			if(fx[v] > max(fx[u] + 1,a[v])){
				fx[v] = max(fx[u] + 1,a[v]);
				pq.push({fx[v],v});
			}
		}
	}
	
	int res = INF;
	for(int i = 1;i <= n;i++){
		res = min(res,2 * max(step[i],fx[i]));
	}
	
	for(int i = 1;i <= n;i++){
		for(auto v : adj[i]){
			res = min(res,2 * max(step[i],fx[v]) + 1);
		}
	}
	
	
	cout << res;
	
	
}

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