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;
}