Submission #886145

#	Time	Username	Problem	Language	Result	Execution time	Memory
886145		vjudge1	Airplane (NOI23_airplane)	C++17	22 / 100	70 ms	16008 KiB

Main

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

typedef array<int, 2> info; // min k, min altitude

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <int> arr(n + 1);
	vector <vector<int> > adj(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector <info> about(n + 1, {inf, inf}), ans;
	priority_queue<pair<info, int> > pq;
	pq.push({{0, 0}, 1});
	bitset <200005> vis;
	while(!pq.empty()) {
		int node = pq.top().second;
		info values = pq.top().first;
		pq.pop();
		if(vis[node]) continue;
		vis[node] = 1;
		int k = -values[0], mn = values[1];
		// cout << node << ": " << k << " " << mn << "\n";
		k++, mn--;
		for(auto to:adj[node]) {
			int alt = arr[to];
			info infTo = {k + max(0ll, alt - k), max(mn, alt)};
			if(infTo[0] < about[to][0]) {
				about[to] = infTo;
				if(to == n) {
					ans.push_back(infTo);
				}
				infTo[0] *= -1;
				pq.push({infTo, to});
			}
		}
	}
	int aaa = inf;
	for(auto it:ans) {
		// cout << it[0] << " " << it[1] << "\n";
		aaa = min(aaa, it[0] + max(0ll, it[1]));
	}
	cout << aaa;
}

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