結果
問題 | No.1865 Make Cycle |
ユーザー | titia |
提出日時 | 2022-03-06 02:32:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,393 ms / 3,000 ms |
コード長 | 2,120 bytes |
コンパイル時間 | 725 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 290,796 KB |
最終ジャッジ日時 | 2024-07-03 18:13:06 |
合計ジャッジ時間 | 29,901 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,509 ms
270,340 KB |
testcase_01 | AC | 1,121 ms
273,068 KB |
testcase_02 | AC | 1,578 ms
275,352 KB |
testcase_03 | AC | 914 ms
273,040 KB |
testcase_04 | AC | 1,498 ms
286,888 KB |
testcase_05 | AC | 216 ms
106,664 KB |
testcase_06 | AC | 1,673 ms
280,232 KB |
testcase_07 | AC | 1,510 ms
281,172 KB |
testcase_08 | AC | 1,889 ms
288,060 KB |
testcase_09 | AC | 220 ms
106,972 KB |
testcase_10 | AC | 1,756 ms
283,088 KB |
testcase_11 | AC | 1,652 ms
287,084 KB |
testcase_12 | AC | 1,409 ms
270,324 KB |
testcase_13 | AC | 1,391 ms
276,224 KB |
testcase_14 | AC | 1,185 ms
277,060 KB |
testcase_15 | AC | 1,768 ms
278,804 KB |
testcase_16 | AC | 1,924 ms
284,856 KB |
testcase_17 | AC | 186 ms
100,460 KB |
testcase_18 | AC | 227 ms
108,064 KB |
testcase_19 | AC | 2,393 ms
290,796 KB |
testcase_20 | AC | 37 ms
54,128 KB |
testcase_21 | AC | 37 ms
52,944 KB |
testcase_22 | AC | 36 ms
53,512 KB |
testcase_23 | AC | 37 ms
53,056 KB |
ソースコード
import sys input = sys.stdin.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)