oj.uz

Submission #828121

# Submission time Handle Problem Language Result Execution time Memory
828121 2023-08-17T05:31:54 Z 반딧불(#10380) Airplane (NOI23_airplane) C++17
0 / 100
 91 ms 22116 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;
int ex[400002], ey[400002];
vector<int> link[200002];
ll arr[200002];
ll dist1[200002]; bool visited1[200002];
ll distn[200002]; bool visitedn[200002];
priority_queue<dat> pq;
ll ans = LLONG_MAX;

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

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

	pq.push(dat(n, 0));
	while(!pq.empty()){
		dat tmp = pq.top(); pq.pop();
		if(visitedn[tmp.x]) continue;
		visitedn[tmp.x] = 1, distn[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 dist1: %lld, distn: %lld\n", i, dist1[i], distn[i]);
		#endif
		ans = min(ans, max(dist1[i], distn[i]) * 2);
	}
	for(int i=1; i<=m; i++){
		if(arr[ex[i]] == arr[ey[i]]){
			ans = min(ans, dist1[ex[i]] + distn[ey[i]] + 1);
			ans = min(ans, distn[ex[i]] + dist1[ey[i]] + 1);
		}
	}
	printf("%lld", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  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]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~
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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 82 ms 21016 KB Output is correct
3 Correct 91 ms 21464 KB Output is correct
4 Correct 77 ms 21688 KB Output is correct
5 Incorrect 89 ms 22116 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 82 ms 21016 KB Output is correct
3 Correct 91 ms 21464 KB Output is correct
4 Correct 77 ms 21688 KB Output is correct
5 Incorrect 89 ms 22116 KB Output isn't correct
6 Halted 0 ms 0 KB -