Submission #886238

#	Time	Username	Problem	Language	Result	Execution time	Memory
886238		vjudge1	Airplane (NOI23_airplane)	C++17	0 / 100	192 ms	604 KiB

Main

#include <bits/stdc++.h>

#define lli long long int
#define MP make_pair
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
#define pb push_back

const int N = 2e3+5;
const int M = 4e3+5;
const int MOD = 1e9+7;
const int INF = 1e9 + 500;
using namespace std;

void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}
int n,m,q;
vector<int> a(N, 0);
vector<vector<int> > adj(N, vector<int>());
vector<int> dp1, dp2;
vector<int> vis(N, 0);
void bfs(int src, vector<int> &sp) {
    priority_queue<array<int,2> > que;
    sp.assign(n + 3, INF);
    sp[src] = 0;
    que.push({0, src});
    while(que.size()) {
        auto cur = que.top();
        que.pop();
        for(auto c : adj[cur[1]]) {
            if(vis[c]) continue;
            if(sp[c] != INF) continue;

            sp[c] = max(cur[0] + 1 , a[c]);
            que.push({sp[c], c});
        }
    } 

}


void solve() {
    cin>>n>>m;
    REP(i,n) cin>>a[i + 1];
    for(int i = 1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vector<array<int,2> > srt(n);
    for(int i = 1 ;i<=n; i++) {
        srt[i - 1] = {a[i], i};
    }
    int ans = INF;
    sort(srt.rbegin(), srt.rend());
    for(auto c : srt) {
    bfs(1, dp1);
    bfs(n, dp2);
    
    ans = min(ans , dp1[c[1]] + dp2[c[1]]);
    vis[c[1]] = 1;
    }
    cout<<ans<<"\n";
}

signed main() {
    // fastio();
    solve();
}   

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
      |                          ^
Main.cpp:45:5: note: in expansion of macro 'REP'
   45 |     REP(i,n) cin>>a[i + 1];
      |     ^~~

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