結果
問題 |
No.1865 Make Cycle
|
ユーザー |
👑 |
提出日時 | 2022-04-07 00:32:35 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 121 ms / 3,000 ms |
コード長 | 955 bytes |
コンパイル時間 | 110 ms |
コンパイル使用メモリ | 5,120 KB |
実行使用メモリ | 24,960 KB |
最終ジャッジ日時 | 2024-11-27 21:20:35 |
合計ジャッジ時間 | 3,651 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
local n, q = io.read("*n", "*n") local ea, eb = {}, {} local ccnt, parent = {}, {} for i = 1, n do ccnt[i] = 0 parent[i] = {} end for iq = 1, q do local a, b = io.read("*n", "*n") ea[iq], eb[iq] = a, b ccnt[a] = ccnt[a] + 1 parent[b][iq] = true end local tasks = {} for i = 1, n do if ccnt[i] == 0 then table.insert(tasks, i) end end local done = 0 local function rm() while done < #tasks do done = done + 1 local src = tasks[done] for pi, _u in pairs(parent[src]) do local p = ea[pi] ccnt[p] = ccnt[p] - 1 if ccnt[p] == 0 then table.insert(tasks, p) end end parent[src] = {} end end rm() if done == n then print(-1) os.exit() end for iq = q, 1, -1 do local a, b = ea[iq], eb[iq] if parent[b][iq] then parent[b][iq] = nil ccnt[a] = ccnt[a] - 1 if ccnt[a] == 0 then table.insert(tasks, a) rm() end end if done == n then print(iq) break end end