답안 #886145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886145	2023-12-11T13:50:37 Z	vjudge1	Airplane (NOI23_airplane)	C++17	22 / 100	70 ms	16008 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-