Submission #1105605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105605		12345678	Airplane (NOI23_airplane)	C++17	41 / 100	1083 ms	15244 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, m, a[nx], u, v, vl[nx], rvl[nx], vs[nx], dist[nx], res=1e9;
vector<int> d[nx];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>a[i], vl[i]=rvl[i]=1e9;
    for (int i=1; i<=m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u); 
    vl[1]=rvl[n]=0;
    pq.push({0, 1});
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (auto v:d[u]) if (vl[v]>max(cw+1, a[v])) vl[v]=max(cw+1, a[v]), pq.push({vl[v], v});
    }
    pq.push({0, n});
    for (int i=1; i<=n; i++) vs[i]=0;
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (auto v:d[u]) if (rvl[v]>max(cw+1, a[v])) rvl[v]=max(cw+1, a[v]), pq.push({rvl[v], v});
    }
    /*
    cout<<"vl ";
    for (int i=1; i<=n; i++) cout<<vl[i]<<' ';
    cout<<'\n';
    cout<<"rvl ";
    for (int i=1; i<=n; i++) cout<<rvl[i]<<' ';
    cout<<'\n';
    */
    for (int t=1; t<=n; t++)
    {
        int mx=a[t];
        for (int i=1; i<=n ;i++) dist[i]=1e9, vs[i]=0;
        for (int i=1; i<=n; i++) if (vl[i]<=mx) dist[i]=0, pq.push({0, i});
        while (!pq.empty())
        {
            auto [cw, u]=pq.top();
            pq.pop();
            if (vs[u]) continue;
            vs[u]=1;
            for (auto v:d[u]) if (a[v]<=mx&&dist[v]>cw+1) dist[v]=cw+1, pq.push({dist[v], v});
        }
        for (int i=1; i<=n; i++) if (rvl[i]<=mx) res=min(res, 2*mx+dist[i]);
    }
    cout<<res;
}

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