---
# System prepended metadata

title: D. Toss a Coin to Your Graph...

---

# D. Toss a Coin to Your Graph...
Đề bài : https://codeforces.com/contest/1679/problem/D

Chặt nhị phân rồi còn lại là check cycle với tìm max path.

Code : 
:::spoiler
```cpp 
#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i) 
#define rev(i, a, b) for (int i = (a); i >= (b); --i) 
#define ll long long
#define pii pair<int, int>
#define pli pair<long long, int>
#define pb push_back
#define fi first
#define pii pair<int, int>
#define se second
#define lb long double

using namespace std; 
const int mxn = 2e5 + 5;
const ll MOD = 998244353;
const ll INF = 1e9;
vector<int> vec[mxn];
ll a[mxn];
bool valid[mxn];
int vis[mxn], par[mxn], len[mxn];
int n, m, k;

bool dfs(int u)
{
    vis[u] = 1;
    for (int v : vec[u]) if (valid[v] && vis[v] != 2)
    {
        if (vis[v] == 1) return 1;
        if (dfs(v)) return 1;
    }
    vis[u] = 2;
    return 0;
}

bool solve(ll val)
{
    rep(i, 1, n) 
    {
        vis[i] = valid[i] = 0;
        if (a[i] <= val) valid[i] = 1;
    }
    rep(i, 1, n) if (!vis[i] && dfs(i))
        return 1;

    rep(i, 1, n) par[i]= 0;
    rep(u, 1, n) if (valid[u])
        for(int v : vec[u]) ++par[v]; 

    vector<int> t;
    rep(i, 1, n) len[i] = 0;
    rep(i, 1, n) if (valid[i] && par[i] == 0)
        t.pb(i);

    int res = -1;
    while(t.size())
    {
        int u = t.back(); t.pop_back();
        res = max(res, len[u]);
        for (int v : vec[u]) if (valid[v])
        {
            if (--par[v] == 0) t.pb(v);
            len[v] = max(len[v], len[u] + 1);
        }
    }

    return (res + 1 >= k);
}

int main(){
    //freopen("H:\\file_txt\\input.txt", "r", stdin);
    //freopen("H:\\file_txt\\output.txt", "w", stdout);
    cin >> n >> m >> k;
    rep(i, 1, n) scanf("%lli", &a[i]);
    rep(i, 1, m)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        vec[u].pb(v);
    }

    ll l = 0, r = 1000000001;
    while(l < r)
    {
        ll mid = (l + r)>>1;
        if (solve(mid)) r = mid;
        else l = mid + 1;
    }
    if (l == 1e9 + 1) l = -1;
    cout << l;
}
```
:::