Codeforces Round #791 (Div. 2) D. Toss a Coin to Your Graph...

D. Toss a Coin to Your Graph…

二分，dfs, toposort, dp

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long LL;
typedef vector<int> VI;
const int N = 2e5 + 10;
VI edg[N];
int a[N], b[N];
int in[N], dp[N];
int n, m;
LL k;
void init() {
    for (int i = 1; i <= n; i ++ ) 
        dp[i] = 0, in[i] = 0;
}
bool check(int mid) {
    int cnt = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (a[i] <= b[mid]) {
            cnt ++;
            for (auto j : edg[i]) 
                if (a[j] <= b[mid])
                    in[j] ++;
        }
    }
    VI res;
    for (int i = 1; i <= n; i ++ )
        if (a[i] <= b[mid] && in[i] == 0)
            res.PB(i);
    for (int i = 0; i < res.size(); i ++ ) {
        int u = res[i];
        for (auto j : edg[u]) 
            if (a[j] <= b[mid]) {
                dp[j] = max(dp[j], dp[u] + 1);
                in[j] --;
                if (!in[j]) res.PB(j);
            }
    }
    int mx = 0;
    for (int i = 1; i <= n; i ++ ) 
        mx = max(mx, dp[i]);
    if (res.size() < cnt || mx >= k - 1) return 1;
    else return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    while (m -- ) {
        int u, v;
        cin >> u >> v;
        edg[u].PB(v);
    }
    int l = 1, r = n;
    while (l < r) {
        init();
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (check(l)) cout << b[l] << endl;
    else cout << -1 << endl;
    return 0;
}