結果

問題 No.1166 NADA DNA
ユーザー 👑 obakyan
提出日時 2021-08-09 17:07:16
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 1,633 ms / 3,000 ms
コード長 1,314 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 5,376 KB
実行使用メモリ 19,584 KB
最終ジャッジ日時 2024-09-21 16:09:08
合計ジャッジ時間 25,678 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

local n, len = io.read("*n", "*n", "*l")
local s = {}
for i = 1, n do
  s[i] = io.read()
end
local ea, eb, ec = {}, {}, {}
local eidx = {}
for i = 1, n - 1 do for j = i + 1, n do
  local v = 0
  for k = 1, len do
    if s[i]:sub(k, k) ~= s[j]:sub(k, k) then v = v + 1 end
  end
  table.insert(ea, i)
  table.insert(eb, j)
  table.insert(ec, v)
  table.insert(eidx, #ea)
end end
table.sort(eidx, function(a, b) return ec[a] < ec[b] end)


local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local function kruskal(n, linenum)
  local parent = uf_initialize(n)
  local totalcost = 0
  local used = 0
  for i = 1, linenum do
    local ei = eidx[i]
    local c, i1, i2 = ec[ei], ea[ei], eb[ei]
    local r1, r2 = uf_findroot(i1, parent), uf_findroot(i2, parent)
    parent[i1], parent[i2] = r1, r2
    if r1 ~= r2 then
      parent[r2] = r1
      parent[i2] = r1
      totalcost = totalcost + c
      used = used + 1
      if used == n - 1 then break end
    end
  end
  return totalcost
end

print(kruskal(n, #ea))
0