Submission #1213298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213298		vtnoo	Airplane (NOI23_airplane)	C++20	0 / 100	44 ms	13744 KiB

Main

/*
 * Es onda subo subo subo y bajo bajo bajo
 * lo más optimo sería caer justo en el punto minimax y bajar
 */ 
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>

#define pb push_back
#define snd second
#define fst first
#define forn(i,n) for(int i=0;i<n;++i)
#define forsn(i,s,n) for(int i=s; i<n; ++i)
#define all(x) x.begin(), x.end()
#define imp(x) for(auto __:x)cout<<__<<" "; cout<<endl;
#define sz(c) int((c).size())
#define mset(a,v) memset((a), (v), sizeof(a));

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int N=200005, inf=1e9;
int n, m, a[N];
vi adj[N];

vi dijkstra(int s){
	priority_queue<ii, vector<ii>, greater<ii>> q;
	q.push({0, s});
	vi h(n+1, inf);
	h[s]=0;
	//~ cout<<"======================"<<endl;
	while(!q.empty()){
		auto [t, u]=q.top();
		q.pop();
		for(auto v:adj[u]){
			t=max(h[u]+1, a[v]);
			//~ cout<<u<<" "<<v<<" "<<t<<endl;
			if(t<h[v]){
				h[v]=t;
				q.push({h[v], v});
			} 
		}
	}
	return h;
}

int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	forn(i,n)cin>>a[i+1];
	forn(i,m){
		int u,v;cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi timeFromS=dijkstra(1);
	vi timeFromE=dijkstra(n);
	//~ forn(i,sz(timeFromS))cout<<timeFromS[i]<<" ";
	//~ cout<<endl;
	//~ forn(i,sz(timeFromE))cout<<timeFromE[i]<<" ";
	//~ cout<<endl;
	int ans=1e9;
	forsn(i,1,n+1){
		ans=min(ans, max(timeFromS[i], timeFromE[i])*2);
	}
	cout<<ans<<endl;
}

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