Submission #1312465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312465		sakuda00	Airplane (NOI23_airplane)	C++20	100 / 100	380 ms	24656 KiB

Main

#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
int N;
bool chmin(ll&a, ll b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
vector<vector<int>> G;
vector<ll> A;
ll inf = (1LL << 60);
int cst(int x, int y) {
	return (N * x) + y;
}
vector<pair<ll, ll> > dist(int st) {
	vector<pair<ll, ll> > res(N, {inf,-1});
	priority_queue<pair<ll,  int>, vector<pair<ll, int>>, greater<pair<ll, int>> > pq;
	pq.push({0, st});
	res[st] = {0LL, A[st]};
	while (!pq.empty()) {
		auto tp = pq.top();
		ll d = tp.first;
		int v = tp.second;
		pq.pop();
		if (res[v].first < d) continue;
		for (auto nv : G[v]) {
			ll ncst = max(d + 1, A[nv]);
			if (ncst < res[nv].first) {
				res[nv] = {ncst, max(res[v].second, A[nv])};
				pq.push({ncst, nv});
			}
		}
	}
	return res;
}
int main() {
	int M;cin >> N >> M;
	G.assign(N, {});
	A.assign(N, 0);
	for (int i = 0;i < N;i++) cin >> A[i];
	for (int i = 0;i < M;i++) {
		int a, b;cin >> a >>b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	auto dist0 = dist(0);
	auto distN = dist(N - 1);
	ll res = inf;
	for (int v = 0;v < N;v++) {
		if (dist0[v].second == A[v] and distN[v].second == A[v]) {
			//cout << v+1 << " " << dist0[v].first << " " << distN[v].first << endl;
			res = min(res, dist0[v].first + distN[v].first);

		}
	}
	cout << res << endl;
}

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