oj.uz

Submission #940020

# Submission time Handle Problem Language Result Execution time Memory
940020 2024-03-07T04:02:10 Z browntoad Airplane (NOI23_airplane) C++14
22 / 100
 75 ms 19644 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for(int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppi pair<pii, int>
#define pip pair<int, pii>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


const ll maxn = 2e5+5;
const ll maxm = 1e4+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

vector<int> g[maxn];
vector<int> h(maxn);

int n, m;

int dis[maxn][2];

vector<bool> occ(maxn);
void dij(int st, bool typ){
    // source st, typ = 0: it is n
    fill(ALL(occ), 0);
    REP1(i, n) dis[i][typ] = inf;
    priority_queue<pii> pq;

    dis[st][typ] = 0;
    pq.push({0, st});
    while(SZ(pq)){
        pii tp = pq.top(); pq.pop();
        int u = tp.s;
        if (occ[u]) continue;
        occ[u] = 1;
        for(auto v:g[u]){
            if (dis[v][typ] > max(h[v], dis[u][typ]+1)){
                dis[v][typ] = max(h[v], dis[u][typ]+1);
                pq.push({dis[v][typ], v});
            }
        }
    }
}
signed main(){
    IOS();
    cin>>n>>m;
    REP1(i, n) cin>>h[i];
    vector<pii> ee;
    REP(i, m){
        int u, v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        ee.pb({u, v});
    }

    dij(1, 0); dij(n, 1);
    int ans = inf;
    REP1(i, n){
        ans = min(ans, max(dis[i][0], dis[i][1])*2);
    }
    for (auto e:ee){
        int u = e.f, v = e.s;
        ans = min({ans, max(dis[u][0], dis[v][1])*2+1, max(dis[v][0], dis[u][1])*2+1});
    }
    cout<<ans<<endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 65 ms 19060 KB Output is correct
3 Correct 61 ms 19136 KB Output is correct
4 Correct 62 ms 19132 KB Output is correct
5 Correct 71 ms 19228 KB Output is correct
6 Correct 64 ms 19644 KB Output is correct
7 Correct 75 ms 19208 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7608 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 4 ms 7768 KB Output is correct
8 Correct 4 ms 7768 KB Output is correct
9 Incorrect 3 ms 7768 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 3 ms 7608 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7772 KB Output is correct
7 Correct 4 ms 7768 KB Output is correct
8 Correct 4 ms 7768 KB Output is correct
9 Incorrect 3 ms 7768 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 65 ms 19060 KB Output is correct
3 Correct 61 ms 19136 KB Output is correct
4 Correct 62 ms 19132 KB Output is correct
5 Correct 71 ms 19228 KB Output is correct
6 Correct 64 ms 19644 KB Output is correct
7 Correct 75 ms 19208 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 2 ms 7512 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7608 KB Output is correct
13 Correct 3 ms 7516 KB Output is correct
14 Correct 3 ms 7772 KB Output is correct
15 Correct 4 ms 7768 KB Output is correct
16 Correct 4 ms 7768 KB Output is correct
17 Incorrect 3 ms 7768 KB Output isn't correct
18 Halted 0 ms 0 KB -