Submission #893365

#	Time	Username	Problem	Language	Result	Execution time	Memory
893365		fdnfksd	Airplane (NOI23_airplane)	C++14	100 / 100	378 ms	41724 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=4e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll d[3][maxn];
ll n;
vector<ll>g[maxn];
ll a[maxn];
void dij(ll t,ll s)
{
    for(int i=1;i<=n;i++) d[t][i]=inf;
    d[t][s]=0;
    priority_queue<pli,vector<pli>,greater<pli>>pq;
    pq.push({d[t][s],s});
    while(!pq.empty())
    {
        ll u=pq.top().se;
        pq.pop();
        for(int v:g[u])
        {
            if(d[t][v]>max(d[t][u]+1,a[v]))
            {
                d[t][v]=max(d[t][u]+1,a[v]);
                pq.push({d[t][v],v});
            }
        }
    }
}
ll m;
ll ans=inf;
void solve()
{
    cin >> n >> m ;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for(int i=1;i<=m;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dij(0,1);
    dij(1,n);
    for(int i=1;i<=n;i++)
    {
        if(abs(d[0][i]-d[1][i])<=1) ans=min(ans,d[0][i]+d[1][i]);
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen("c.INP","r",stdin);
    //freopen("c.OUT","w",stdout);
    solve();
}

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