結果
問題 | No.1865 Make Cycle |
ユーザー | NatsubiSogan |
提出日時 | 2022-03-10 03:00:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,305 ms / 3,000 ms |
コード長 | 543 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 87,120 KB |
実行使用メモリ | 217,060 KB |
最終ジャッジ日時 | 2023-10-12 04:37:20 |
合計ジャッジ時間 | 22,122 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,019 ms
176,372 KB |
testcase_01 | AC | 641 ms
144,120 KB |
testcase_02 | AC | 1,054 ms
185,960 KB |
testcase_03 | AC | 336 ms
107,812 KB |
testcase_04 | AC | 577 ms
170,496 KB |
testcase_05 | AC | 801 ms
187,896 KB |
testcase_06 | AC | 1,035 ms
181,340 KB |
testcase_07 | AC | 807 ms
172,192 KB |
testcase_08 | AC | 1,166 ms
197,728 KB |
testcase_09 | AC | 744 ms
186,128 KB |
testcase_10 | AC | 942 ms
189,844 KB |
testcase_11 | AC | 896 ms
184,204 KB |
testcase_12 | AC | 835 ms
168,724 KB |
testcase_13 | AC | 1,019 ms
172,192 KB |
testcase_14 | AC | 658 ms
156,316 KB |
testcase_15 | AC | 1,162 ms
198,680 KB |
testcase_16 | AC | 1,259 ms
199,392 KB |
testcase_17 | AC | 852 ms
170,920 KB |
testcase_18 | AC | 767 ms
190,864 KB |
testcase_19 | AC | 1,305 ms
217,060 KB |
testcase_20 | AC | 73 ms
71,004 KB |
testcase_21 | AC | 74 ms
71,024 KB |
testcase_22 | AC | 73 ms
71,016 KB |
testcase_23 | AC | 73 ms
71,268 KB |
ソースコード
import sys sys.setrecursionlimit(10 ** 6) def dfs(v): visit[v] = 1 for u in G[v]: if visit[u] == 1 or (not visit[u] and dfs(u)): return 1 visit[v] = 2 return 0 n, q = map(int, input().split()) E = [] for _ in range(q): a, b = map(int, input().split()) a -= 1; b -= 1 E.append((a, b)) l, r = -1, q + 1 while r - l > 1: m = (l + r) // 2 G = [[] for _ in range(n)] for a, b in E[:m]: G[a].append(b) visit = [0] * n f = False for i in range(n): if not visit[i]: f |= dfs(i) if f: r = m else: l = m print(r if r <= q else -1)