結果
問題 | No.1865 Make Cycle |
ユーザー | titia |
提出日時 | 2022-03-06 02:34:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,484 ms / 3,000 ms |
コード長 | 2,167 bytes |
コンパイル時間 | 1,214 ms |
コンパイル使用メモリ | 86,936 KB |
実行使用メモリ | 292,156 KB |
最終ジャッジ日時 | 2023-10-12 07:26:11 |
合計ジャッジ時間 | 34,678 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,679 ms
274,952 KB |
testcase_01 | AC | 1,271 ms
272,700 KB |
testcase_02 | AC | 1,626 ms
277,936 KB |
testcase_03 | AC | 934 ms
273,164 KB |
testcase_04 | AC | 1,646 ms
292,156 KB |
testcase_05 | AC | 269 ms
106,524 KB |
testcase_06 | AC | 1,845 ms
281,904 KB |
testcase_07 | AC | 1,393 ms
277,120 KB |
testcase_08 | AC | 2,150 ms
290,748 KB |
testcase_09 | AC | 280 ms
108,872 KB |
testcase_10 | AC | 2,105 ms
286,540 KB |
testcase_11 | AC | 1,949 ms
288,384 KB |
testcase_12 | AC | 1,733 ms
272,560 KB |
testcase_13 | AC | 1,410 ms
280,036 KB |
testcase_14 | AC | 1,518 ms
279,884 KB |
testcase_15 | AC | 2,102 ms
282,000 KB |
testcase_16 | AC | 2,358 ms
283,608 KB |
testcase_17 | AC | 256 ms
103,756 KB |
testcase_18 | AC | 282 ms
112,356 KB |
testcase_19 | AC | 2,484 ms
290,124 KB |
testcase_20 | AC | 75 ms
71,492 KB |
testcase_21 | AC | 81 ms
71,472 KB |
testcase_22 | AC | 80 ms
71,264 KB |
testcase_23 | AC | 81 ms
71,092 KB |
ソースコード
import sys import io, os input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline N,Q=map(int,input().split()) EDGE=[list(map(int,input().split())) for i in range(Q)] for i in range(Q): EDGE[i][0]-=1 EDGE[i][1]-=1 def calc(qind): E=[[] for i in range(N)] E_INV=[[] for i in range(N)] for i in range(qind): x,y=EDGE[i] E[x].append(y) E_INV[y].append(x) # DFSして帰り際にTOPに点を放り込んでいる。 # NOWで現在地点、USEINDで、どこの辺まで既に見たか、を調べている。 def Top_sort(E): Parent=[-1]*N USEIND=[0]*N TOP=[] for ROOT in range(N): if Parent[ROOT]!=-1: continue Parent[ROOT]=ROOT NOW=ROOT while NOW!=ROOT or USEIND[ROOT]!=len(E[ROOT]): if USEIND[NOW]==len(E[NOW]): TOP.append(NOW) NOW=Parent[NOW] elif E[NOW][USEIND[NOW]]==Parent[NOW]: USEIND[NOW]+=1 else: NEXT=E[NOW][USEIND[NOW]] USEIND[NOW]+=1 if Parent[NEXT]==-1: Parent[NEXT]=NOW NOW=NEXT TOP.append(ROOT) return TOP[::-1] USE=[0]*N SCC=[] # SCCを調べるための逆順DFS。 # やっていることはhttps://manabitimes.jp/math/1250 などと同じ。 def dfs2(x): Q=[x] USE[x]=1 ANS=[] while Q: x=Q.pop() ANS.append(x) for to in E_INV[x]: if USE[to]==0: USE[to]=1 Q.append(to) return ANS TOP_SORT=Top_sort(E) for x in TOP_SORT: if USE[x]==0: SCC.append(dfs2(x)) for i in range(len(SCC)): if len(SCC[i])>1: return True return False if calc(Q)==False: print(-1) else: OK=Q NG=1 while OK>NG+1: mid=(OK+NG)//2 if calc(mid)==True: OK=mid else: NG=mid print(OK)