oj.uz

Submission #886145

# Submission time Handle Problem Language Result Execution time Memory
886145 2023-12-11T13:50:37 Z vjudge1 Airplane (NOI23_airplane) C++17
22 / 100
 70 ms 16008 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

typedef array<int, 2> info; // min k, min altitude

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <int> arr(n + 1);
	vector <vector<int> > adj(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector <info> about(n + 1, {inf, inf}), ans;
	priority_queue<pair<info, int> > pq;
	pq.push({{0, 0}, 1});
	bitset <200005> vis;
	while(!pq.empty()) {
		int node = pq.top().second;
		info values = pq.top().first;
		pq.pop();
		if(vis[node]) continue;
		vis[node] = 1;
		int k = -values[0], mn = values[1];
		// cout << node << ": " << k << " " << mn << "\n";
		k++, mn--;
		for(auto to:adj[node]) {
			int alt = arr[to];
			info infTo = {k + max(0ll, alt - k), max(mn, alt)};
			if(infTo[0] < about[to][0]) {
				about[to] = infTo;
				if(to == n) {
					ans.push_back(infTo);
				}
				infTo[0] *= -1;
				pq.push({infTo, to});
			}
		}
	}
	int aaa = inf;
	for(auto it:ans) {
		// cout << it[0] << " " << it[1] << "\n";
		aaa = min(aaa, it[0] + max(0ll, it[1]));
	}
	cout << aaa;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 60 ms 16008 KB Output is correct
3 Correct 61 ms 15952 KB Output is correct
4 Correct 57 ms 15952 KB Output is correct
5 Correct 70 ms 15952 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 62 ms 15952 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 428 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Incorrect 2 ms 600 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 428 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Incorrect 2 ms 600 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 60 ms 16008 KB Output is correct
3 Correct 61 ms 15952 KB Output is correct
4 Correct 57 ms 15952 KB Output is correct
5 Correct 70 ms 15952 KB Output is correct
6 Correct 70 ms 15952 KB Output is correct
7 Correct 62 ms 15952 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 428 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 3 ms 600 KB Output is correct
25 Incorrect 2 ms 600 KB Output isn't correct
26 Halted 0 ms 0 KB -