結果
問題 | No.1865 Make Cycle |
ユーザー | titia |
提出日時 | 2022-03-06 02:40:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,753 ms / 3,000 ms |
コード長 | 2,066 bytes |
コンパイル時間 | 259 ms |
コンパイル使用メモリ | 87,060 KB |
実行使用メモリ | 279,464 KB |
最終ジャッジ日時 | 2023-09-27 16:16:49 |
合計ジャッジ時間 | 23,946 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,118 ms
265,952 KB |
testcase_01 | AC | 749 ms
221,112 KB |
testcase_02 | AC | 1,274 ms
274,972 KB |
testcase_03 | AC | 584 ms
202,200 KB |
testcase_04 | AC | 1,006 ms
274,824 KB |
testcase_05 | AC | 201 ms
102,008 KB |
testcase_06 | AC | 1,203 ms
274,512 KB |
testcase_07 | AC | 1,128 ms
262,932 KB |
testcase_08 | AC | 1,343 ms
275,748 KB |
testcase_09 | AC | 215 ms
101,080 KB |
testcase_10 | AC | 1,238 ms
264,484 KB |
testcase_11 | AC | 1,265 ms
266,948 KB |
testcase_12 | AC | 1,127 ms
271,488 KB |
testcase_13 | AC | 1,169 ms
267,272 KB |
testcase_14 | AC | 851 ms
244,884 KB |
testcase_15 | AC | 1,388 ms
270,984 KB |
testcase_16 | AC | 1,484 ms
277,436 KB |
testcase_17 | AC | 199 ms
98,536 KB |
testcase_18 | AC | 222 ms
103,576 KB |
testcase_19 | AC | 1,753 ms
279,464 KB |
testcase_20 | AC | 68 ms
71,276 KB |
testcase_21 | AC | 68 ms
71,224 KB |
testcase_22 | AC | 67 ms
71,152 KB |
testcase_23 | AC | 65 ms
71,204 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: if len(dfs2(x))>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)