Submission #1173571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173571		PenguinsAreCute	Airplane (NOI23_airplane)	C++20	100 / 100	669 ms	43208 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int,int>;
int h[601210], dist[2][601210];
vector<int> adj[601210];
void dijkstra(int x, int id) {
	priority_queue<ii,vector<ii>,greater<ii>> pq;
	dist[id][x]=0; pq.push({0,x}); while(pq.size()) {
		auto [d, i] = pq.top(); pq.pop();
		if(d != dist[id][i]) continue;
		for(auto j: adj[i]) if(max(h[j],d+1) < dist[id][j]) {
			dist[id][j] = max(h[j], d+1);
			pq.push({dist[id][j],j});
		}
	}
}
main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	for(int i=1;i<=n;i++) {cin>>h[i]; h[i]<<=1;}
	for(int u,v,i=1;i<=m;i++) {
		cin >> u >> v;
		adj[u].push_back(n+i);
		adj[v].push_back(n+i);
		adj[n+i].push_back(u);
		adj[n+i].push_back(v);
	}
	for(int i=0;i<2;i++) for(int j=0;j<601210;j++) dist[i][j]=2.67e8;
	dijkstra(1,0); dijkstra(n,1);
	int ans = 2.67e8;
	for(int i=1;i<=n+m;i++) ans = min(ans, max(dist[0][i], dist[1][i]));
	cout << ans;
}

Compilation message (stderr)

Main.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main() {
      | ^~~~

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