oj.uz

Submission #891930

# Submission time Handle Problem Language Result Execution time Memory
891930 2023-12-24T13:13:30 Z vjudge1 Airplane (NOI23_airplane) C++17
0 / 100
 56 ms 15440 KB 
#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n,m;
int step[MAX],fx[MAX];
vector<int> adj[MAX];
int a[MAX];

priority_queue<ii,vector<ii>,greater<ii>> pq;

signed main(){
	
	read();
	
	cin >> n >> m;
	
	for(int i = 1;i <= n;i++)cin >> a[i];
	
	for(int i = 1,u,v;i <= m;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	memset(step,0x3f,sizeof step);
	memset(fx,0x3f,sizeof fx);
	
	pq.push({0,1});
	step[1] = 0;
	
	while(!pq.empty()){
		int u = pq.top().Y;
		int d = pq.top().X;
		
		pq.pop();
		
		if(d != step[u])continue;
		
		for(auto v : adj[u]){
			if(step[v] > max(step[u] + 1,a[v])){
				step[v] = max(step[u] + 1,a[v]);
				pq.push({step[v],v});
			}
		}
	}
	
	pq.push({0,n});
	fx[n] = 0;
	
	while(!pq.empty()){
		int u = pq.top().Y;
		int d = pq.top().X;
		
		pq.pop();
		
		if(d != fx[u])continue;
		
		for(auto v : adj[u]){
			if(fx[v] > max(fx[u] + 1,a[v])){
				fx[v] = max(fx[u] + 1,a[v]);
				pq.push({fx[v],v});
			}
		}
	}
	
	int res = 0x3f;
	for(int i = 1;i <= n;i++){
		res = min(res,2 * max(step[i],fx[i]));
	}
	
	for(int i = 1;i <= n;i++){
		for(auto v : adj[i]){
			if(a[v] == a[i])
			res = min(res,fx[i] + step[v] + 1);
		}
	}
	
	
	cout << res;
	
	
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Incorrect 56 ms 15440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Incorrect 2 ms 7260 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 7256 KB Output is correct
2 Incorrect 56 ms 15440 KB Output isn't correct
3 Halted 0 ms 0 KB -