結果
問題 | No.1865 Make Cycle |
ユーザー |
![]() |
提出日時 | 2022-03-04 21:55:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 573 ms / 3,000 ms |
コード長 | 828 bytes |
コンパイル時間 | 247 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 158,928 KB |
最終ジャッジ日時 | 2024-07-18 20:15:51 |
合計ジャッジ時間 | 9,904 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
""" 1865: 二分探索でok """ import sys from sys import stdin from collections import deque N,Q = map(int,stdin.readline().split()) AB = [] for i in range(Q): A,B = map(int,stdin.readline().split()) A -= 1 B -= 1 AB.append( (A,B) ) L = 0 R = Q+1 while R-L != 1: M = (L+R)//2 lis = [ [] for i in range(N) ] inlis = [0] * N for i in range(M): a,b = AB[i] lis[a].append(b) inlis[b] += 1 q = deque([]) for i in range(N): if inlis[i] == 0: q.append(i) end = 0 while q: v = q.popleft() end += 1 for nex in lis[v]: inlis[nex] -= 1 if inlis[nex] == 0: q.append(nex) if end == N: L = M else: R = M if R == Q+1: R = -1 print (R)