oj.uz

Submission #930683

# Submission time Handle Problem Language Result Execution time Memory
930683 2024-02-20T09:22:55 Z dubabuba Airplane (NOI23_airplane) C++14
0 / 100
 134 ms 15256 KB 
#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 dis[2][mxn];
int alt[2][mxn];

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

	memset(dis[0], -1, sizeof dis[0]);
	memset(dis[1], -1, sizeof dis[1]);
	memset(alt[0], -1, sizeof alt[0]);
	memset(alt[1], -1, sizeof alt[1]);

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

		if(dis[0][u] > -1) continue;
		dis[0][u] = d;
		alt[0][u] = h;

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

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

		if(dis[1][u] > -1) continue;
		dis[1][u] = d;
		alt[1][u] = h;

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

	int ans = INT_MAX;
	for(int i = 1; i <= n; i++)
	if(alt[0][i] == alt[1][i] && alt[0][i] != -1)
		ans = min(ans, dis[0][i] + dis[1][i]);

	cout << ans << endl;
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Incorrect 134 ms 15256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Incorrect 3 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Incorrect 3 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Incorrect 134 ms 15256 KB Output isn't correct
3 Halted 0 ms 0 KB -