Submission #1102328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102328		HiepVu217	Airplane (NOI23_airplane)	C++17	100 / 100	288 ms	28348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 17;
const long long oo = 1e18;
int n, m, a[N];
vector <int> adj[N];
long long ds[N], dt[N], ans;
void dijkstra (int s, long long d[])
{
    priority_queue <pair <long long, int>> pq;
    for (int i = 1; i <= n; ++i)
    {
        d[i] = oo;
    }
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty())
    {
        auto [du, u] = pq.top();
        du = -du;
        pq.pop();
        if (du > d[u])
        {
            continue;
        }
        for (int v: adj[u])
        {
            long long z = max (1LL * a[v], du + 1);
            if (z < d[v])
            {
                d[v] = z;
                pq.push({-z, v});
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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);
    }
    dijkstra (1, ds);
    dijkstra (n, dt);
    ans = oo;
    for (int i = 1; i <= n; ++i)
    {
        ans = min (ans, max (ds[i], dt[i]) * 2);
        for (int j: adj[i])
        {
            ans = min (ans, max (ds[i], dt[j]) * 2 + 1);
        }
    }
    cout << ans;
}

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