結果
問題 | No.1293 2種類の道路 |
ユーザー |
👑 |
提出日時 | 2021-07-22 09:05:10 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 1,214 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 6,940 KB |
実行使用メモリ | 20,228 KB |
最終ジャッジ日時 | 2024-07-17 14:35:30 |
合計ジャッジ時間 | 3,963 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
local n, d, w = io.read("*n", "*n", "*n")local function uf_initialize(n)local parent = {}local rank = {}for i = 1, n doparent[i] = irank[i] = 1endreturn parent, rankendlocal function uf_findroot(idx, parent)local idx_update = idxwhile parent[idx] ~= idx doidx = parent[idx]endwhile parent[idx_update] ~= idx doparent[idx_update], idx_update = idx, parent[idx_update]endreturn idxendlocal p1 = uf_initialize(n)local p2, p2rank = uf_initialize(n)for i = 1, d dolocal a, b = io.read("*n", "*n")local ra, rb = uf_findroot(a, p1), uf_findroot(b, p1)p1[rb], p1[b] = ra, raendfor i = 1, w dolocal a, b = io.read("*n", "*n")local ra, rb = uf_findroot(a, p2), uf_findroot(b, p2)if ra ~= rb thenp2rank[ra] = p2rank[ra] + p2rank[rb]p2rank[rb] = falsep2[rb], p2[b] = ra, raendendlocal hub = {}local ret = {}for i = 1, n dohub[i] = {}ret[i] = 0endfor i = 1, n dolocal a = uf_findroot(i, p1)local b = uf_findroot(i, p2)if not hub[a][b] thenhub[a][b] = trueret[a] = ret[a] + p2rank[b]endendlocal ans = -nfor i = 1, n dolocal a = uf_findroot(i, p1)ans = ans + ret[a]endprint(ans)