Submission #1122612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122612		nhphuc	Airplane (NOI23_airplane)	C++20	100 / 100	508 ms	36776 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int inf = 1e16;

struct min_height {
    int d, h, u;

    min_height (int _d, int _h, int _u) : d(_d), h(_h), u(_u) {}

    bool operator < (const min_height &oth) const {
        return (d < oth.d || (d == oth.d && h < oth.h));
    }

    bool operator > (const min_height &oth) const {
        return (d > oth.d || (d == oth.d && h > oth.h));
    }
};

struct max_height {
    int d, h, u;

    max_height (int _d, int _h, int _u) : d(_d), h(_h), u(_u) {}

    bool operator < (const max_height &oth) const {
        return (d < oth.d || (d == oth.d && h > oth.h));
    }

    bool operator > (const max_height &oth) const {
        return (d > oth.d || (d == oth.d && h < oth.h));
    }
};

const int N = 200200;

int n, m, a[N];
pair<int, int> f1[N][2], f2[N][2];
vector<int> adj[N];

bool intersect (int l, int r, int u, int v){
    if (v >= l && r >= v){
        return true;
    }
    if (u >= l && r >= u){
        return true;
    }
    if (l >= u && l <= v){
        return true;
    }
    if (r >= u && r <= v){
        return true;
    }
    return false;
}

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        f1[i][0] = f1[i][1] = {inf, inf};
        f2[i][0] = f2[i][1] = {inf, -1};
    }
    for (int i = 1; i <= m; ++i){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // solve for f1
    if (true){
        priority_queue<min_height, vector<min_height>, greater<min_height>> pq;
        // solve for 1
        f1[1][0] = {0, 0}; pq.push(min_height(0, 0, 1));
        while (pq.size()){
            auto [d, h, u] = pq.top(); pq.pop();
            auto [X, Y] = f1[u][0];
            if (X < d || (X == d && Y < h)){
                continue;
            }
            for (int v : adj[u]){
                int nd = max(d + 1, a[v]);
                int nh = (h > a[v] ? h - 1 : a[v]);
                auto [X, Y] = f1[v][0];
                if (X > nd || (X == nd && Y > nh)){
                    f1[v][0] = {nd, nh};
                    pq.push(min_height(nd, nh, v));
                }
            }
        }
        // solve for n
        f1[n][1] = {0, 0}; pq.push(min_height(0, 0, n));
        while (pq.size()){
            auto [d, h, u] = pq.top(); pq.pop();
            auto [X, Y] = f1[u][1];
            if (X < d || (X == d && Y < h)){
                continue;
            }
            for (int v : adj[u]){
                int nd = max(d + 1, a[v]);
                int nh = (h > a[v] ? h - 1 : a[v]);
                auto [X, Y] = f1[v][1];
                if (X > nd || (X == nd && Y > nh)){
                    f1[v][1] = {nd, nh};
                    pq.push(min_height(nd, nh, v));
                }
            }
        }
    }
    // solve for f2
    if (true){
        priority_queue<max_height, vector<max_height>, greater<max_height>> pq;
        // solve for 1
        f2[1][0] = {0, 0}; pq.push(max_height(0, 0, 1));
        while (pq.size()){
            auto [d, h, u] = pq.top(); pq.pop();
            auto [X, Y] = f2[u][0];
            if (X < d || (X == d && Y > h)){
                continue;
            }
            for (int v : adj[u]){
                int nd = max(d + 1, a[v]);
                int nh = max(h + 1, a[v]);
                auto [X, Y] = f2[v][0];
                if (X > nd || (X == nd && Y < nh)){
                    f2[v][0] = {nd, nh};
                    pq.push(max_height(nd, nh, v));
                }
            }
        }
        // solve for n
        f2[n][1] = {0, 0}; pq.push(max_height(0, 0, n));
        while (pq.size()){
            auto [d, h, u] = pq.top(); pq.pop();
            auto [X, Y] = f2[u][1];
            if (X < d || (X == d && Y > h)){
                continue;
            }
            for (int v : adj[u]){
                int nd = max(d + 1, a[v]);
                int nh = max(h + 1, a[v]);
                auto [X, Y] = f2[v][1];
                if (X > nd || (X == nd && Y < nh)){
                    f2[v][1] = {nd, nh};
                    pq.push(max_height(nd, nh, v));
                }
            }
        }
    }
    int ans = inf;
    for (int i = 1; i <= n; ++i){
        int d1 = f1[i][0].first;
        int d2 = f2[i][1].first;
        int l = f1[i][0].second, r = f2[i][0].second;
        int u = f1[i][1].second, v = f2[i][1].second;
        if (intersect(l, r, u, v)){
            ans = min(ans, d1 + d2);
        } else {
            ans = min(ans, d1 + d2 + max(u - r, l - v));
        }
    }
    cout << ans << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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