結果

問題 No.1865 Make Cycle
ユーザー brthyyjpbrthyyjp
提出日時 2022-03-07 20:59:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 718 ms / 3,000 ms
コード長 1,373 bytes
コンパイル時間 465 ms
コンパイル使用メモリ 86,764 KB
実行使用メモリ 213,428 KB
最終ジャッジ日時 2023-09-29 23:28:53
合計ジャッジ時間 12,316 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 462 ms
143,364 KB
testcase_01 AC 339 ms
127,428 KB
testcase_02 AC 510 ms
156,588 KB
testcase_03 AC 312 ms
139,280 KB
testcase_04 AC 426 ms
153,380 KB
testcase_05 AC 150 ms
93,564 KB
testcase_06 AC 480 ms
151,596 KB
testcase_07 AC 438 ms
145,488 KB
testcase_08 AC 551 ms
167,284 KB
testcase_09 AC 148 ms
93,140 KB
testcase_10 AC 516 ms
167,676 KB
testcase_11 AC 530 ms
160,784 KB
testcase_12 AC 459 ms
144,844 KB
testcase_13 AC 431 ms
141,520 KB
testcase_14 AC 395 ms
135,204 KB
testcase_15 AC 632 ms
168,004 KB
testcase_16 AC 607 ms
175,608 KB
testcase_17 AC 138 ms
90,136 KB
testcase_18 AC 145 ms
94,640 KB
testcase_19 AC 718 ms
213,428 KB
testcase_20 AC 82 ms
71,460 KB
testcase_21 AC 79 ms
71,776 KB
testcase_22 AC 77 ms
71,460 KB
testcase_23 AC 78 ms
71,464 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