結果
問題 | No.1865 Make Cycle |
ユーザー |
![]() |
提出日時 | 2022-03-04 21:49:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 598 ms / 3,000 ms |
コード長 | 1,144 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 173,564 KB |
最終ジャッジ日時 | 2024-07-18 19:59:49 |
合計ジャッジ時間 | 9,611 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
mod = 1000000007 eps = 10**-9 def main(): import sys from collections import deque input = sys.stdin.buffer.readline N, Q = map(int, input().split()) AB = [(0, 0)] for _ in range(Q): AB.append(tuple(map(int, input().split()))) ok = Q + 1 ng = 0 mid = (ok + ng) // 2 while ok - ng > 1: adj = [[] for _ in range(N + 1)] in_num = [0] * (N + 1) for a, b in AB[1:mid+1]: adj[a].append(b) in_num[b] += 1 que = deque() seen = [0] * (N + 1) for v in range(1, N + 1): if in_num[v] == 0: seen[v] = 1 que.append(v) while que: v = que.popleft() for u in adj[v]: in_num[u] -= 1 if in_num[u] == 0: if not seen[u]: seen[u] = 1 que.append(u) if sum(seen) == N: ng = mid else: ok = mid mid = (ok + ng) // 2 if ok == Q + 1: print(-1) else: print(ok) if __name__ == '__main__': main()