Submission #1313158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313158		miniob	Airplane (NOI23_airplane)	C++20	100 / 100	200 ms	17508 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int wys[200007];
int odl_do_gory[200007];
int odl_do_dolu[200007];
vector<int> graph[200007];
int n;

void djikstraz1()
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, 1});
	while(!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();
		int odlcur = cur.first;
		int gdzie = cur.second;
		if(odl_do_gory[gdzie] < odlcur)
		{
			continue;
		}
		for(auto x : graph[gdzie])
		{
			if(odl_do_dolu[x] > max(odlcur + 1, wys[x]))
			{
				odl_do_dolu[x] = max(odlcur + 1, wys[x]);
				pq.push({odl_do_dolu[x], x});
			}
		}
	}
}

void djikstrazn(int n)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({0, n});
	while(!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();
		int odlcur = cur.first;
		int gdzie = cur.second;
		if(odl_do_gory[gdzie] < odlcur)
		{
			continue;
		}
		for(auto x : graph[gdzie])
		{
			if(odl_do_gory[x] > max(odlcur + 1, wys[x]))
			{
				odl_do_gory[x] = max(odlcur + 1, wys[x]);
				pq.push({odl_do_gory[x], x});
			}
		}
	}
}

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int m, a, b;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		odl_do_gory[i] = odl_do_dolu[i] = INT_MAX / (int)2;
		cin >> wys[i];
	}
	odl_do_dolu[1] = 0;
	odl_do_gory[n] = 0;
	for(int i = 0; i < m; i++)
	{
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	djikstraz1();
	djikstrazn(n);
	int wyn = INT_MAX;
	for(int i = 1; i <= n; i++)
	{
		//cout << odl_do_dolu[i] << " " << odl_do_gory[i] << endl;
		wyn = min(wyn, 2 * max(odl_do_dolu[i], odl_do_gory[i]));
		for(auto x : graph[i])
		{
			wyn = min(wyn, 2 * max(odl_do_dolu[i], odl_do_gory[x]) + 1);
			wyn = min(wyn, 2 * max(odl_do_dolu[x], odl_do_gory[i]) + 1);
		}
	}
	cout << wyn << endl;
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37