oj.uz

Submission #929281

# Submission time Handle Problem Language Result Execution time Memory
929281 2024-02-18T04:34:21 Z dubabuba Airplane (NOI23_airplane) C++14
0 / 100
 136 ms 35932 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 = 1e6 + 10;
int dis[mxn], a[mxn], n, m;
vector<int> adj[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, -1, sizeof dis);
	priority_queue<pii> pq;
	pq.push(MP(0, 1));

	while(pq.size()) {
		int d = -pq.top().ff;
		int u = pq.top().ss;
		pq.pop();

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

		for(int v : adj[u])
			if(dis[v] == -1)
				pq.push(MP(-(d + max(1, abs(a[v] - a[u]))), v));
	}

	cout << dis[n] << endl;
	return 0;
}

/*
6 7
0 100 10 7 8 0
1 3
1 2
2 3
3 4
3 5
2 5
2 6
*/

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Incorrect 136 ms 35932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Incorrect 136 ms 35932 KB Output isn't correct
3 Halted 0 ms 0 KB -