Submission #1128421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128421		pemguimn	Airplane (NOI23_airplane)	C++17	0 / 100	182 ms	19220 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 5, INF = 1e18 + 5;

int n, m, w[N]; pii a[N];
vector<int> adj[N];

vector<int> go(int s){
    vector<bool> mark(n + 1, false);
    vector<int> d(n + 1, INF);
    d[s] = 0;
    for(int i = 1; i <= n; i++){
        int j = a[i].second;
        for(int x : adj[j]){
            if(mark[x]) d[j] = min(d[j], d[x] + 1 + max(0LL, w[j] - w[x] - 1));
        }
        for(int x : adj[j]){
            if(mark[x]) d[x] = min(d[x], d[j] + 1);
        }
        mark[a[i].second] = true;
    }
    return d;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first; a[i].second = i;
        w[i] = a[i].first;
    }
    for(int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        adj[x].push_back(y), adj[y].push_back(x);
    }
    sort(a + 1, a + n + 1);
    vector<int> d1 = go(1);
    vector<int> dn = go(n);
    int ans = INF;
    for(int i = 2; i < n; i++){
        ans = min(ans, d1[i] + dn[i]);
    }
    cout << ans << '\n';
    return 0;
}

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