oj.uz

Submission #828135

# Submission time Handle Problem Language Result Execution time Memory
828135 2023-08-17T05:39:12 Z 박상훈(#10381) Airplane (NOI23_airplane) C++17
100 / 100
 724 ms 58324 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 4e18;

vector<int> adj[600600];
ll a[600600], dist[2][600600];

void dijkstra(int n, int s, ll dist[]){
	fill(dist+1, dist+n+1, INF);
	dist[s] = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, s});

	while(!pq.empty()){
		auto [d, cur] = pq.top(); pq.pop();
		if (d > dist[cur]) continue;

		for (auto &nxt:adj[cur]){
			ll nd = max(d+1, a[nxt]);
			if (nd < dist[nxt]){
				dist[nxt] = nd;
				pq.push({nd, nxt});
			}
		}
	}
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i=1;i<=n;i++) scanf("%lld", a+i);
	for (int i=1;i<=n;i++) a[i] *= 2;

	for (int i=1;i<=m;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(n+i);
		adj[y].push_back(n+i);

		adj[n+i].push_back(x);
		adj[n+i].push_back(y);
	}

	dijkstra(n+m, 1, dist[0]);
	dijkstra(n+m, n, dist[1]);

	ll ans = INF;
	for (int i=1;i<=n+m;i++) ans = min(ans, max(dist[0][i], dist[1][i]));
	printf("%lld\n", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:35:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                         ~~~~~^~~~~~~~~~~~~
Main.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 122 ms 34892 KB Output is correct
3 Correct 97 ms 35000 KB Output is correct
4 Correct 101 ms 35092 KB Output is correct
5 Correct 120 ms 35008 KB Output is correct
6 Correct 99 ms 38968 KB Output is correct
7 Correct 98 ms 38904 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14416 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 9 ms 14612 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14648 KB Output is correct
14 Correct 12 ms 14680 KB Output is correct
15 Correct 9 ms 14804 KB Output is correct
16 Correct 9 ms 14800 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 7 ms 14420 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14416 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 9 ms 14612 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 8 ms 14548 KB Output is correct
13 Correct 8 ms 14648 KB Output is correct
14 Correct 12 ms 14680 KB Output is correct
15 Correct 9 ms 14804 KB Output is correct
16 Correct 9 ms 14800 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 7 ms 14420 KB Output is correct
19 Correct 8 ms 14676 KB Output is correct
20 Correct 8 ms 14552 KB Output is correct
21 Correct 11 ms 14676 KB Output is correct
22 Correct 8 ms 14676 KB Output is correct
23 Correct 8 ms 14672 KB Output is correct
24 Correct 9 ms 14556 KB Output is correct
25 Correct 9 ms 14676 KB Output is correct
26 Correct 10 ms 14696 KB Output is correct
27 Correct 9 ms 14676 KB Output is correct
28 Correct 10 ms 14804 KB Output is correct
29 Correct 10 ms 14804 KB Output is correct
30 Correct 10 ms 14804 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 122 ms 34892 KB Output is correct
3 Correct 97 ms 35000 KB Output is correct
4 Correct 101 ms 35092 KB Output is correct
5 Correct 120 ms 35008 KB Output is correct
6 Correct 99 ms 38968 KB Output is correct
7 Correct 98 ms 38904 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 6 ms 14412 KB Output is correct
10 Correct 9 ms 14412 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 8 ms 14548 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 8 ms 14548 KB Output is correct
17 Correct 8 ms 14548 KB Output is correct
18 Correct 9 ms 14612 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 8 ms 14548 KB Output is correct
21 Correct 8 ms 14648 KB Output is correct
22 Correct 12 ms 14680 KB Output is correct
23 Correct 9 ms 14804 KB Output is correct
24 Correct 9 ms 14800 KB Output is correct
25 Correct 10 ms 14804 KB Output is correct
26 Correct 7 ms 14420 KB Output is correct
27 Correct 8 ms 14676 KB Output is correct
28 Correct 8 ms 14552 KB Output is correct
29 Correct 11 ms 14676 KB Output is correct
30 Correct 8 ms 14676 KB Output is correct
31 Correct 8 ms 14672 KB Output is correct
32 Correct 9 ms 14556 KB Output is correct
33 Correct 9 ms 14676 KB Output is correct
34 Correct 10 ms 14696 KB Output is correct
35 Correct 9 ms 14676 KB Output is correct
36 Correct 10 ms 14804 KB Output is correct
37 Correct 10 ms 14804 KB Output is correct
38 Correct 10 ms 14804 KB Output is correct
39 Correct 302 ms 39088 KB Output is correct
40 Correct 251 ms 38300 KB Output is correct
41 Correct 221 ms 38236 KB Output is correct
42 Correct 224 ms 38220 KB Output is correct
43 Correct 228 ms 38292 KB Output is correct
44 Correct 243 ms 38224 KB Output is correct
45 Correct 274 ms 38176 KB Output is correct
46 Correct 245 ms 38268 KB Output is correct
47 Correct 267 ms 38268 KB Output is correct
48 Correct 243 ms 38228 KB Output is correct
49 Correct 352 ms 39156 KB Output is correct
50 Correct 349 ms 38908 KB Output is correct
51 Correct 276 ms 38864 KB Output is correct
52 Correct 500 ms 48928 KB Output is correct
53 Correct 454 ms 47684 KB Output is correct
54 Correct 461 ms 47636 KB Output is correct
55 Correct 522 ms 47488 KB Output is correct
56 Correct 637 ms 57144 KB Output is correct
57 Correct 720 ms 55096 KB Output is correct
58 Correct 716 ms 55692 KB Output is correct
59 Correct 724 ms 55480 KB Output is correct
60 Correct 544 ms 58324 KB Output is correct
61 Correct 693 ms 55388 KB Output is correct
62 Correct 557 ms 57212 KB Output is correct
63 Correct 536 ms 57312 KB Output is correct
64 Correct 588 ms 57360 KB Output is correct
65 Correct 557 ms 57400 KB Output is correct
66 Correct 647 ms 54652 KB Output is correct
67 Correct 708 ms 55128 KB Output is correct