Submission #1122728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122728		peacebringer1667	Airplane (NOI23_airplane)	C++20	63 / 100	224 ms	18884 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
const int inf = 1e17;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

vector <int> vec[maxn];
int a[maxn],dist[maxn][2];

bool mark[maxn];
set <pair<int,pir>> s;
priority_queue <pir,vector<pir>,greater<pir>> pq;

vector <int> val_list;

void input(int n,int m){
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	
	while (m--){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
}

void prepare(int n){
	for (int i = 1 ; i <= n ; i++) val_list.push_back(a[i]);
	
	sort(val_list.begin(),val_list.end());
	val_list.erase(unique(val_list.begin(),val_list.end()),val_list.end());
}

void refresh(int n,int state){
	pq = priority_queue <pir,vector<pir>,greater<pir>>();
	s.clear();
	for (int i = 0 ; i <= n + 1 ; i++) mark[i] = 0,dist[i][state] = inf;
}

void dijkstra(int source,int state,int n){
	refresh(n,state);
	
	//source = 1 or n. a[source] = 0
	s.insert({a[source],{0,source}});
	
	for (int cap : val_list){
		while (pq.size() || (s.size() && (*s.begin()).fi <= cap)){
			if (pq.size()){
				pir t = pq.top();
				pq.pop();
				
				int u = t.se,w = t.fi;
				if (mark[u]) continue;
				
				mark[u] = 1;
				if (a[u] == cap) dist[u][state] = w;
				
				for (int v : vec[u])
				   s.insert({a[v],{max(w + 1,a[v]),v}});
			}
			
			while (s.size()){
				pair<int,pir> t = *s.begin();
				if (t.fi > cap) break;
				s.erase(t);
				
				pq.push({t.se.fi,t.se.se});
			}
		}
	}
}

int calc(int n){
	int res = inf;
	
	for (int i = 1 ; i <= n ; i++)
	  res = min(res,dist[i][0] + dist[i][1]);
	  
	return res;
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,m;
	cin >> n >> m;
	input(n,m);
	
	prepare(n);
	
	dijkstra(1,0,n);
	dijkstra(n,1,n);
	
	cout << calc(n);
	

	return 0;
}

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