oj.uz

Submission #828279

# Submission time Handle Problem Language Result Execution time Memory
828279 2023-08-17T07:37:15 Z 반딧불(#10380) Airplane (NOI23_airplane) C++17
63 / 100
 1000 ms 56460 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
	int x; ll dist; /// dist: 실제 시간, off: arr[i] 값에 비해 초과된 시간
	dat(){}
	dat(int x, ll dist): x(x), dist(dist){}

	bool operator<(const dat &r)const{
		return dist > r.dist;
	}
};

int n, m, s, e;
vector<int> link[600002];
ll arr[600002];
ll dists[600002]; bool visiteds[600002];
ll diste[600002]; bool visitede[600002];
priority_queue<dat> pq;
ll ans = LLONG_MAX;

int main(){
	scanf("%d %d", &n, &m);
	s = 1, e = n;
	for(int i=1; i<=n; i++) scanf("%lld", &arr[i]), arr[i] *= 2;
	for(int i=1; i<=m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		int z = ++n;
		link[x].push_back(z);
		link[y].push_back(z);
		link[z].push_back(x);
		link[z].push_back(y);
	}

	pq.push(dat(s, 0));
	while(!pq.empty()){
		dat tmp = pq.top(); pq.pop();
		if(visiteds[tmp.x]) continue;
		visiteds[tmp.x] = 1, dists[tmp.x] = tmp.dist;
		for(auto y: link[tmp.x]){
			pq.push(dat(y, max(tmp.dist+1, arr[y])));
		}
	}

	pq.push(dat(e, 0));
	while(!pq.empty()){
		dat tmp = pq.top(); pq.pop();
		if(visitede[tmp.x]) continue;
		visitede[tmp.x] = 1, diste[tmp.x] = tmp.dist;
		for(auto y: link[tmp.x]){
			pq.push(dat(y, max(tmp.dist+1, arr[y])));
		}
	}

	for(int i=1; i<=n; i++){
		#ifdef TEST
		printf("%d dists: %lld, diste: %lld\n", i, dists[i], diste[i]);
		#endif
		ans = min(ans, max(dists[i], diste[i]));
	}
	printf("%lld", ans);
}

Compilation message

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 110 ms 38404 KB Output is correct
3 Correct 113 ms 38468 KB Output is correct
4 Correct 110 ms 38408 KB Output is correct
5 Correct 113 ms 38444 KB Output is correct
6 Correct 126 ms 39740 KB Output is correct
7 Correct 137 ms 39756 KB Output is correct
8 Correct 9 ms 14396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 14660 KB Output is correct
7 Correct 8 ms 14660 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 11 ms 14624 KB Output is correct
10 Correct 10 ms 14596 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 9 ms 14676 KB Output is correct
13 Correct 9 ms 14620 KB Output is correct
14 Correct 10 ms 14664 KB Output is correct
15 Correct 11 ms 14804 KB Output is correct
16 Correct 13 ms 14804 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 10 ms 14396 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 11 ms 14660 KB Output is correct
7 Correct 8 ms 14660 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 11 ms 14624 KB Output is correct
10 Correct 10 ms 14596 KB Output is correct
11 Correct 8 ms 14548 KB Output is correct
12 Correct 9 ms 14676 KB Output is correct
13 Correct 9 ms 14620 KB Output is correct
14 Correct 10 ms 14664 KB Output is correct
15 Correct 11 ms 14804 KB Output is correct
16 Correct 13 ms 14804 KB Output is correct
17 Correct 10 ms 14804 KB Output is correct
18 Correct 10 ms 14396 KB Output is correct
19 Correct 11 ms 14676 KB Output is correct
20 Correct 11 ms 14568 KB Output is correct
21 Correct 11 ms 14680 KB Output is correct
22 Correct 12 ms 14656 KB Output is correct
23 Correct 9 ms 14568 KB Output is correct
24 Correct 11 ms 14568 KB Output is correct
25 Correct 11 ms 14664 KB Output is correct
26 Correct 11 ms 14676 KB Output is correct
27 Correct 14 ms 14816 KB Output is correct
28 Correct 13 ms 14796 KB Output is correct
29 Correct 12 ms 14804 KB Output is correct
30 Correct 11 ms 14896 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 110 ms 38404 KB Output is correct
3 Correct 113 ms 38468 KB Output is correct
4 Correct 110 ms 38408 KB Output is correct
5 Correct 113 ms 38444 KB Output is correct
6 Correct 126 ms 39740 KB Output is correct
7 Correct 137 ms 39756 KB Output is correct
8 Correct 9 ms 14396 KB Output is correct
9 Correct 10 ms 14420 KB Output is correct
10 Correct 6 ms 14420 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 11 ms 14660 KB Output is correct
15 Correct 8 ms 14660 KB Output is correct
16 Correct 9 ms 14676 KB Output is correct
17 Correct 11 ms 14624 KB Output is correct
18 Correct 10 ms 14596 KB Output is correct
19 Correct 8 ms 14548 KB Output is correct
20 Correct 9 ms 14676 KB Output is correct
21 Correct 9 ms 14620 KB Output is correct
22 Correct 10 ms 14664 KB Output is correct
23 Correct 11 ms 14804 KB Output is correct
24 Correct 13 ms 14804 KB Output is correct
25 Correct 10 ms 14804 KB Output is correct
26 Correct 10 ms 14396 KB Output is correct
27 Correct 11 ms 14676 KB Output is correct
28 Correct 11 ms 14568 KB Output is correct
29 Correct 11 ms 14680 KB Output is correct
30 Correct 12 ms 14656 KB Output is correct
31 Correct 9 ms 14568 KB Output is correct
32 Correct 11 ms 14568 KB Output is correct
33 Correct 11 ms 14664 KB Output is correct
34 Correct 11 ms 14676 KB Output is correct
35 Correct 14 ms 14816 KB Output is correct
36 Correct 13 ms 14796 KB Output is correct
37 Correct 12 ms 14804 KB Output is correct
38 Correct 11 ms 14896 KB Output is correct
39 Correct 422 ms 39844 KB Output is correct
40 Correct 243 ms 38952 KB Output is correct
41 Correct 244 ms 38960 KB Output is correct
42 Correct 308 ms 39028 KB Output is correct
43 Correct 269 ms 39056 KB Output is correct
44 Correct 370 ms 39000 KB Output is correct
45 Correct 309 ms 38960 KB Output is correct
46 Correct 308 ms 38992 KB Output is correct
47 Correct 305 ms 39024 KB Output is correct
48 Correct 282 ms 39008 KB Output is correct
49 Correct 417 ms 39984 KB Output is correct
50 Correct 359 ms 39616 KB Output is correct
51 Correct 347 ms 39672 KB Output is correct
52 Correct 657 ms 49348 KB Output is correct
53 Correct 683 ms 48264 KB Output is correct
54 Correct 607 ms 48196 KB Output is correct
55 Correct 699 ms 47224 KB Output is correct
56 Correct 947 ms 56460 KB Output is correct
57 Correct 923 ms 55860 KB Output is correct
58 Execution timed out 1014 ms 55948 KB Time limit exceeded
59 Halted 0 ms 0 KB -