結果

問題 No.1865 Make Cycle
ユーザー brthyyjpbrthyyjp
提出日時 2022-03-07 20:59:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 711 ms / 3,000 ms
コード長 1,373 bytes
コンパイル時間 581 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 208,924 KB
最終ジャッジ日時 2024-07-22 17:25:33
合計ジャッジ時間 10,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 437 ms
146,252 KB
testcase_01 AC 307 ms
124,764 KB
testcase_02 AC 475 ms
147,676 KB
testcase_03 AC 257 ms
128,508 KB
testcase_04 AC 375 ms
149,476 KB
testcase_05 AC 111 ms
86,748 KB
testcase_06 AC 450 ms
145,684 KB
testcase_07 AC 417 ms
147,752 KB
testcase_08 AC 537 ms
166,904 KB
testcase_09 AC 103 ms
86,592 KB
testcase_10 AC 478 ms
158,404 KB
testcase_11 AC 493 ms
157,548 KB
testcase_12 AC 408 ms
140,032 KB
testcase_13 AC 400 ms
130,148 KB
testcase_14 AC 386 ms
137,572 KB
testcase_15 AC 542 ms
158,848 KB
testcase_16 AC 568 ms
167,124 KB
testcase_17 AC 100 ms
84,596 KB
testcase_18 AC 108 ms
87,488 KB
testcase_19 AC 711 ms
208,924 KB
testcase_20 AC 39 ms
53,760 KB
testcase_21 AC 38 ms
54,016 KB
testcase_22 AC 39 ms
53,888 KB
testcase_23 AC 39 ms
53,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
def cycle_detectable_topological_sort(g, ind):
    V = len(g)
    order = []
    depth = [-1]*V
    for i in range(V):
        if not ind[i]:
            order.append(i)
            depth[i] = 0

    q = deque(order)
    while q:
        v = q.popleft()
        cur_depth = depth[v]
        for u in g[v]:
            ind[u] -= 1
            if not ind[u]:
                depth[u] = max(depth[u], cur_depth+1)
                q.append(u)
                order.append(u)
    if len(order) == V:
        return (order, depth)
    else:
        return (None, None)

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, q = map(int, input().split())
AB = []
for i in range(q):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    AB.append((a, b))

g = [[] for i in range(n)]
ind = [0]*n
for a, b in AB:
    g[a].append(b)
    ind[b] += 1

order, _ = cycle_detectable_topological_sort(g, ind)
if order is not None:
    print(-1)
    exit()

def is_ok(x):
    g = [[] for i in range(n)]
    ind = [0]*n
    for i in range(x+1):
        a, b = AB[i]
        g[a].append(b)
        ind[b] += 1
    order, _ = cycle_detectable_topological_sort(g, ind)
    return order is None

ng = -1
ok = q-1
while ng+1<ok:
    mid = (ng+ok)//2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)
0