Toss a Coin to Your Graph... (Codeforces 1679D)
Tags: DP, graphs

One day Masha was walking in the park and found a graph under a tree... Surprised? Did you think that this problem would have some logical and reasoned story? No way! So, the problem...Masha has an oriented graph which $$$i$$$-th vertex contains some positive integer $$$a_i$$$. Initially Masha can put a coin at some vertex. In one operation she can move a coin placed in some vertex $$$u$$$ to any other vertex $$$v$$$ such that there is an oriented edge $$$u \to v$$$ in the graph. Each time when the coin is placed in some vertex $$$i$$$, Masha write down an integer $$$a_i$$$ in her notebook (in particular, when Masha initially puts a coin at some vertex, she writes an integer written at this vertex in her notebook). Masha wants to make exactly $$$k - 1$$$ operations in such way that the maximum number written in her notebook is as small as possible.

Input: The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^{18}$$$) — the number of vertices and edges in the graph, and the number of operation that Masha should make.The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers written in graph vertices.Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u \ne v \le n$$$) — it means that there is an edge $$$u \to v$$$ in the graph.It's guaranteed that graph doesn't contain loops and multi-edges.

Output: Print one integer — the minimum value of the maximum number that Masha wrote in her notebook during optimal coin movements.If Masha won't be able to perform $$$k - 1$$$ operations, print $$$-1$$$.

Note: Graph described in the first and the second examples is illustrated below.  In the first example Masha can initially put a coin at vertex $$$1$$$. After that she can perform three operations: $$$1 \to 3$$$, $$$3 \to 4$$$ and $$$4 \to 5$$$. Integers $$$1, 2, 3$$$ and $$$4$$$ will be written in the notepad.In the second example Masha can initially put a coin at vertex $$$2$$$. After that she can perform $$$99$$$ operations: $$$2 \to 5$$$, $$$5 \to 6$$$, $$$6 \to 2$$$, $$$2 \to 5$$$, and so on. Integers $$$10, 4, 5, 10, 4, 5, \ldots, 10, 4, 5, 10$$$ will be written in the notepad.In the third example Masha won't be able to perform $$$4$$$ operations.

Sample Inputs:
6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

2 1 5
1 1
1 2

1 0 1
1000000000

Sample Outputs:
4

10

-1

1000000000

Solution (Python):
from sys import stdin, stdout
(n, m, k) = [int(x) for x in stdin.readline().split()]
a = [int(x) for x in stdin.readline().split()]
edges = {i: [] for i in range(n)}
for bar in range(m):
    (u, v) = [int(x) - 1 for x in stdin.readline().split()]
    edges[u].append(v)
a_copy = list(set(a))
a_copy.sort()

def check(bound):
    heights = [0] * n
    expanded = [0] * n
    parents = [-1] * n
    for root in range(n):
        if a[root] <= bound and heights[root] == 0:
            stack = [root]
            while len(stack) > 0:
                if heights[stack[-1]] > 0:
                    v = stack.pop()
                    expanded[v] = 2
                    if parents[v] != -1:
                        heights[parents[v]] = max(heights[parents[v]], 1 + heights[v])
                        if heights[parents[v]] >= k:
                            return True
                else:
                    v = stack[-1]
                    heights[v] = 1
                    if heights[v] >= k:
                        return True
                    expanded[v] = 1
                    for w in edges[v]:
                        if a[w] <= bound:
                            if expanded[w] == 1:
                                return True
                            if heights[w] > 0:
                                heights[v] = max(heights[v], 1 + heights[w])
                                if heights[v] >= k:
                                    return True
                            else:
                                parents[w] = v
                                stack.append(w)
    return False
if not check(a_copy[-1]):
    stdout.write('-1\n')
else:
    upper = len(a_copy) - 1
    lower = -1
    while upper - lower > 1:
        candidate = (upper + lower) // 2
        if check(a_copy[candidate]):
            upper = candidate
        else:
            lower = candidate
    stdout.write(str(a_copy[upper]) + '\n')

Solution (Python):
import sys
from collections import Counter
import functools
import math
import random
import sys
import os
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
RI = lambda : list(map(int, sys.stdin.buffer.readline().strip().split()))
RS = lambda : sys.stdin.buffer.readline().strip().decode('ascii')
RLS = lambda : sys.stdin.buffer.readline().strip().decode('ascii').split()
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')
if sys.hexversion == 50924784:
    sys.stdin = open(sys.path[0] + '/data')
''

def solve():
    (n, m, k) = RI()
    a = RI()
    dl = sorted(set(a))
    d = {x: i for (i, x) in enumerate(dl)}
    for i in range(n):
        a[i] = d[a[i]]
    ch = [[] for _ in range(n)]
    for _ in range(m):
        (x, y) = RI()
        ch[x - 1].append(y - 1)
    chn = [len(ch[i]) for i in range(n)]
    sta = [None] * (n + 2)

    def check(x):
        ml = [-1] * n
        for i in range(n):
            if a[i] > x:
                ml[i] = 0
        tm = [0] * n
        tc = [0] * n
        inl = [0] * n

        def dfs(c):
            ei = 0
            sta[ei] = (c, -1)
            ei += 1
            while ei > 0:
                (t, f) = sta[ei - 1]
                if tc[t] == chn[t]:
                    ei -= 1
                    ml[t] = tm[t] + 1
                    if ml[t] >= k or t == c:
                        return ml[t]
                    tc[f] += 1
                    if ml[t] > tm[f]:
                        tm[f] = ml[t]
                    inl[t] = 0
                else:
                    inl[t] = 1
                    for ne in ch[t]:
                        if ml[ne] != -1:
                            tc[t] += 1
                            if ml[ne] > tm[t]:
                                tm[t] = ml[ne]
                        elif inl[ne]:
                            return k
                        else:
                            sta[ei] = (ne, t)
                            ei += 1
            return ml[c]
        for i in range(n):
            if a[i] <= x and dfs(i) >= k:
                return True
        return False
    (l, r) = (0, n)
    if not check(r):
        return print(-1)
    while l < r:
        m = l + r >> 1
        if check(m):
            r = m
        else:
            l = m + 1
    print(dl[l] if l < n else -1)
    return 0
solve()

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
import sys
import os
from itertools import repeat, permutations
import math
import heapq
import random
MOD = 998244353
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp(force_list=False):
    return list(map(int, input().split()))
    if len(re) == 1 and (not force_list):
        return re[0]
    return re

def inst():
    return input().strip()

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def lcm(x, y):
    return x * y / gcd(x, y)

def qmod(a, b, mod=MOD):
    res = 1
    while b:
        if b & 1:
            res = res * a % mod
        b >>= 1
        a = a * a % mod
    return res

def inv(a):
    return qmod(a, MOD - 2)

def query(x, y):
    print('? %d %d' % (x, y))
    stdout.flush()
    return gcd(11 + x, 11 + y)

def C(n, k):
    return fac[n] * inv(fac[k] * fac[n - k] % MOD) % MOD

def my_main():
    kase = 1
    pans = []
    cur = []
    for _ in range(kase):
        (n, m, k) = inp()
        k = min(k, n + 10)
        da = inp(True)
        edges = []
        for i in range(m):
            (u, v) = inp()
            u -= 1
            v -= 1
            edges.append((u, v))
        (G, RG) = ([[] for i in range(n)], [[] for i in range(n)])
        in_dgree = [0] * n
        for (u, v) in edges:
            G[u].append(v)
            RG[v].append(u)
        for d in G:
            d.sort(key=lambda dk: da[dk])
        for d in RG:
            d.sort(key=lambda dk: da[dk])
        mmx = max(da) + 1
        (l, r) = (-1, mmx)
        in_dgree = [0] * n
        q = [0] * n
        dp = [0] * n
        while l < r - 1:
            mid = l + (r - l) // 2
            for i in range(n):
                in_dgree[i] = dp[i] = 0
            for (u, v) in edges:
                if da[u] <= mid and da[v] <= mid:
                    in_dgree[v] += 1
            (ql, qr) = (0, 0)
            tps = 0
            mx = -1
            for i in range(n):
                if in_dgree[i] == 0:
                    q[qr] = i
                    qr += 1
            while ql < qr:
                cur = q[ql]
                ql += 1
                tps += 1
                if da[cur] > mid:
                    continue
                mx = max(mx, dp[cur])
                if mx + 1 >= k:
                    break
                for adj in G[cur]:
                    if da[adj] > mid:
                        break
                    in_dgree[adj] -= 1
                    dp[adj] = max(dp[adj], dp[cur] + 1)
                    if in_dgree[adj] == 0:
                        q[qr] = adj
                        qr += 1
            if mx + 1 >= k or tps != n:
                r = mid
            else:
                l = mid
        if r == mmx:
            print(-1)
        else:
            print(r)
my_main()