oj.uz

Submission #1105604

# Submission time Handle Problem Language Result Execution time Memory
1105604 2024-10-27T01:32:15 Z 12345678 Airplane (NOI23_airplane) C++17
0 / 100
 1000 ms 21300 KB 
#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({vl[v], v});
    }
    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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Execution timed out 1062 ms 21300 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Execution timed out 1062 ms 21300 KB Time limit exceeded
3 Halted 0 ms 0 KB -