結果

問題 No.1166 NADA DNA
ユーザー 👑 obakyanobakyan
提出日時 2021-08-09 17:07:16
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 1,773 ms / 3,000 ms
コード長 1,314 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 5,152 KB
実行使用メモリ 19,432 KB
最終ジャッジ日時 2023-10-21 14:54:48
合計ジャッジ時間 28,760 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 11 ms
4,348 KB
testcase_03 AC 404 ms
7,248 KB
testcase_04 AC 1,594 ms
19,296 KB
testcase_05 AC 1,578 ms
19,296 KB
testcase_06 AC 1,756 ms
19,424 KB
testcase_07 AC 1,580 ms
19,296 KB
testcase_08 AC 1,611 ms
19,424 KB
testcase_09 AC 1,647 ms
19,432 KB
testcase_10 AC 1,583 ms
19,300 KB
testcase_11 AC 1,590 ms
19,424 KB
testcase_12 AC 1,598 ms
19,296 KB
testcase_13 AC 1,607 ms
19,424 KB
testcase_14 AC 1,747 ms
19,424 KB
testcase_15 AC 1,773 ms
19,424 KB
testcase_16 AC 1,760 ms
19,424 KB
testcase_17 AC 1,645 ms
19,424 KB
testcase_18 AC 1,601 ms
19,424 KB
testcase_19 AC 1,606 ms
19,300 KB
testcase_20 AC 1 ms
4,348 KB
testcase_21 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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