EOJ Monthly 2019.2 E. 中位数 （二分+dfs）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
const ll INF=2e9;
int n,m;
int a[N];
vector<int>v[N];
int dis[N];
int vis[N];

int dfs(int mid,int x)
{
   if(vis[x]) return dis[x];
   int tmp=a[x]>=mid?1:-1;
   vis[x]=1;
   for(int i=0;i<v[x].size();i++)
   {
       int t=v[x][i];
       dis[x]=max(dis[x],tmp+dfs(mid,t));
   }
   return dis[x];
}
bool check(int mid)
{
    for(int i=1;i<=n;i++) dis[i]=-INF;
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    dis[1]=a[1]>=mid?1:-1;
    return dfs(mid,n)>=0;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        while(m--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            v[y].push_back(x);
        }
        ll l=0,r=INF;
        ll ans=-1;
        while(l<=r)
        {
            ll mid=l+r>>1;
            if(check(mid))
            {
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        printf("%lld\n",ans);
    }

    return 0;
}