fork(7) download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int a[300005];
  6. vector<int> way[300005];
  7.  
  8. int main(){
  9.     int n;
  10.     scanf("%d", &n);
  11.     int maxval=-1e9;
  12.     for(int i=1; i<=n; i++) scanf("%d", &a[i]), maxval = max(maxval, a[i]);
  13.     for(int i=0; i<n-1; i++){
  14.         int u, v;
  15.         scanf("%d%d", &u, &v);
  16.         way[u].push_back(v);
  17.         way[v].push_back(u);
  18.     }
  19.     int x=0, y=0;
  20.     for(int i=1; i<=n; i++){
  21.         if(a[i] == maxval) x++;
  22.         else if(a[i] == maxval-1) y++;
  23.     }
  24.  
  25.     int res = maxval+2;
  26.  
  27.     for(int i=1; i<=n; i++){
  28.  
  29.         // minus
  30.         if(a[i] == maxval) x--;
  31.         else if(a[i] == maxval-1) y--;
  32.         for(int j=0; j<way[i].size(); j++){
  33.             int pos = way[i][j];
  34.             if(a[pos] == maxval) x--, y++;
  35.             else if(a[pos] == maxval-1) y--;
  36.         }
  37.  
  38.         // check the needed strength and update the answer
  39.         if(x == 0){
  40.             res = min(res, maxval+1);
  41.             if(y == 0) res = min(res, maxval);
  42.         }
  43.  
  44.         // plus
  45.         if(a[i] == maxval) x++;
  46.         else if(a[i] == maxval-1) y++;
  47.         for(int j=0; j<way[i].size(); j++){
  48.             int pos = way[i][j];
  49.             if(a[pos] == maxval) x++, y--;
  50.             else if(a[pos] == maxval-1) y++;
  51.         }
  52.  
  53.     }
  54.  
  55.     printf("%d", res);
  56.  
  57.     return 0;
  58. }
Runtime error #stdin #stdout 0s 23440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B9pjyi
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!