Submission #933109

#	Time	Username	Problem	Language	Result	Execution time	Memory
933109		Jasonwei08	Airplane (NOI23_airplane)	C++14	100 / 100	326 ms	45708 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms (a); memset (a, 0, sizeof a);
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T& a, T b) {
	return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T& a, T b) {
	return (b > a) ? a = b, 1 : 0;
}
using namespace std;
const int N = 5e5 + 5;
int T, n, m, a[N], d[3][N], ans = 1e18;
vector <int> g[N];
void dij (int t, int s) {
	re (i, 1, n, 1) d[t][i] = 1e18;
	d[t][s] = 0;
	priority_queue <PII, vector <PII>, greater<PII> >pq;
	pq.push ({d[t][s], s});
	while (! pq.empty ()) {
		int x = pq.top ().S;
		pq.pop();
		for (int v : g[x]) if (d[t][v] > max (d[t][x] + 1, a[v])) {
				d[t][v] = max (d[t][x] + 1, a[v]);
				pq.push ({d[t][v], v});
			}
	}
}
signed main () {
	cout << fixed << setprecision (0);
	ios :: sync_with_stdio (0), cin.tie (0), cout.tie (0);
	cin >> n >> m;
	int x, y;
	re (i, 1, n, 1) cin >> a[i];
	re (i, 1, m, 1) cin >> x >> y, g[x].pb (y), g[y].pb (x);
	dij (0, 1);
	dij (1, n);
	re (i, 1, n, 1) if (abs (d[0][i] - d[1][i]) <= 1) chkmin (ans, d[0][i] + d[1][i]);
	cout << ans;
	return 0;
}

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