Submission #930712

#	Time	Username	Problem	Language	Result	Execution time	Memory
930712		dubabuba	Airplane (NOI23_airplane)	C++14	0 / 100	187 ms	18308 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 2e5 + 10;
vector<int> adj[mxn];
int a[mxn], n, m;

int dis1[2][mxn], dis2[2][mxn];
int alt1[2][mxn], alt2[2][mxn];

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dis1[0][i] = dis1[1][i] = -1;
		dis1[0][i] = dis1[1][i] = -1;
		dis2[0][i] = dis2[1][i] = -1;
		dis2[0][i] = dis2[1][i] = -1;

		alt1[0][i] = alt1[1][i] = -1;
		alt1[0][i] = alt1[1][i] = -1;
		alt2[0][i] = alt2[1][i] = -1;
		alt2[0][i] = alt2[1][i] = -1;
	}

	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	priority_queue<pair<pii, pii>> pq;
	pq.push(MP(MP(0, 0), MP(0, 1)));
	while(pq.size()) {
		int d = -pq.top().ff.ff;
		int h = -pq.top().ff.ss;
		int x = pq.top().ss.ff;
		int u = pq.top().ss.ss;
		pq.pop();

		int t = (x > 0) ? 1 : 0;
		if(dis1[t][u] > -1) continue;
		dis1[t][u] = d;
		alt1[t][u] = h;
		if(u == 1) {
			dis1[0][u] = dis1[1][u] = 0;
			alt1[0][u] = alt1[1][u] = 0;
		}

		// cout << 1 << " -> " << u << ": " << ((t == 1) ? "up " : "stay ") << d << ' ' << h << endl;

		for(int v : adj[u]) {
			if(h >= a[v]) {
				if(dis1[0][v] == -1)
					pq.push(MP(MP(-(d + 1), -h), MP(0, v)));
				if(dis1[1][v])
					pq.push(MP(MP(-(d + 1), -(h + 1)), MP(1, v)));
			}
			else {
				if(dis1[1][v] == -1)
					pq.push(MP(MP(-(d + a[v] - h), -a[v]), MP(1, v)));
			}
		}
	}

	pq.push(MP(MP(0, 0), MP(0, n)));
	while(pq.size()) {
		int d = -pq.top().ff.ff;
		int h = -pq.top().ff.ss;
		int x = pq.top().ss.ff;
		int u = pq.top().ss.ss;
		pq.pop();

		int t = (x > 0) ? 1 : 0;
		if(dis2[t][u] > -1) continue;
		dis2[t][u] = d;
		alt2[t][u] = h;
		if(u == n) {
			dis2[0][u] = dis2[1][u] = 0;
			alt2[0][u] = alt2[1][u] = 0;
		}

		// cout << n << " -> " << u << ": " << ((t == 1) ? "up " : "stay ") << d << ' ' << h << endl;

		for(int v : adj[u]) {
			if(h >= a[v]) {
				if(dis2[0][v] == -1)
					pq.push(MP(MP(-(d + 1), -h), MP(0, v)));
				if(dis2[1][v])
					pq.push(MP(MP(-(d + 1), -(h + 1)), MP(1, v)));
			}
			else {
				if(dis2[1][v] == -1)
					pq.push(MP(MP(-(d + a[v] - h), -a[v]), MP(1, v)));
			}
		}
	}

	int ans = INT_MAX;
	for(int i = 1; i <= n; i++)
	for(int x = 0; x < 2; x++)
	for(int y = 0; y < 2; y++)
		if(alt1[x][i] == alt2[y][i] && alt1[x][i] != -1)
			ans = min(ans, dis1[x][i] + dis2[y][i]);
	cout << ans << endl;
	return 0;
}

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