結果
問題 |
No.1865 Make Cycle
|
ユーザー |
![]() |
提出日時 | 2022-03-05 00:30:56 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,084 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 249,708 KB |
最終ジャッジ日時 | 2024-09-19 16:14:31 |
合計ジャッジ時間 | 48,903 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 TLE * 1 |
ソースコード
import sys import pypyjit pypyjit.set_param('max_unroll_recursion=-1') sys.setrecursionlimit(200000) n, m = map(int, input().split()) ikeru = [[] for i in range(n)] ikeruinv = [[] for i in range(n)] for j in range(m): a, b = map(int, input().split()) if a == b: continue ikeru[a-1].append((b-1, j + 1)) ikeruinv[b-1].append((a-1, j + 1)) def dfs(a): global ichi if tansaku[a] == 1: return tansaku[a] = 1 for i, v in ikeru[a]: if v <= targ: if tansaku[i] == 0: dfs(i) dat[a] = ichi ichi += 1 return suki = m+3 kirai = -1 while suki - kirai > 1: targ = (suki + kirai) // 2 mode = 1 tansaku = [0 for i in range(n)] tansakuinv = [0 for i in range(n)] dat = [0 for i in range(n)] ichi = 0 for i in range(n): dfs(i) u = [(i, dat[i]) for i in range(n)] u.sort(key=lambda x:-x[1]) for i, d in u: if tansakuinv[i] == 1: continue tansakuinv[i] = 1 for j, v in ikeruinv[i]: if v <= targ: if tansakuinv[j] == 0: mode = 0 break if mode: kirai = targ else: suki = targ if suki > m: print(-1) else: print(suki)