fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define all(x) x.begin(),x.end()
  8. #define task "mpve"
  9. template<class x,class y>
  10.     bool minimize(x &a,const y &b){
  11.         if(a > b){
  12.             a = b;
  13.             return true;
  14.         }else return false;
  15.     }
  16. template<class x,class y>
  17.     bool maximize(x &a,const y &b){
  18.         if(a < b){
  19.             a = b;
  20.             return true;
  21.         }else return false;
  22.     }
  23. typedef pair<int,int> pii;
  24. constexpr int MAXN=1e6,MOD=1e9+7,INF=1e18;
  25. int n,m,l,r,res,ans,k,u,v;
  26. int a,b,w[MAXN],vist[MAXN];
  27. vector<pii> adj[MAXN];
  28. bool check(int w){
  29.     fill(vist+1,vist+n+1,0);
  30.     queue<int> q;
  31.     q.push(a);
  32.     vist[a] = 1;
  33.     while(q.size()){
  34.         int v = q.front();
  35.         q.pop();
  36.         for(pii u : adj[v]){
  37.             if(vist[u.fi]) continue;
  38.             if(u.se <= w){
  39.                 vist[u.fi] = 1;
  40.                 q.push(u.fi);
  41.                 if(u.fi == b) return true;
  42.             }
  43.         }
  44.     }
  45.     return false;
  46. }
  47. int32_t main(){
  48.     ios::sync_with_stdio(false);
  49.     cin.tie(0);cout.tie(0);
  50.     if(fopen(task".INP","r")){
  51.         freopen(task".INP","r",stdin);
  52.         freopen(task".OUT","w",stdout);
  53.     }
  54.     cin >> n >> a >> b;
  55.     for(int i=1;i<=n;i++){
  56.         cin >> w[i];
  57.     }
  58.     u = INF;
  59.     while(cin >> l >> r){
  60.         minimize(u,abs(w[r]-w[l]));
  61.         maximize(v,abs(w[r]-w[l]));
  62.         adj[l].pb(make_pair(r,abs(w[r]-w[l])));
  63.         adj[r].pb(make_pair(l,abs(w[r]-w[l])));
  64.     }
  65.     l = u,r = v;
  66.     ans = -1;
  67.     while(l<=r){
  68.         int m = (l+r)>>1;
  69.         if(check(m)){
  70.             ans = m;
  71.             r = m-1;
  72.         }else l = m+1;
  73.     }
  74.     cout << ans;
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 30744KB
comments (?)
stdin
copy 
7 1 4
20 22 29 30 24 27 26
1 2
1 3
1 4
2 4
2 5
3 4
3 6
4 5
4 6
5 7
6 7
stdout
copy 
2
https://ideone.com/FCJ5Vz
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!