結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー 👑 obakyanobakyan
提出日時 2020-02-15 22:59:48
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 1,216 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 7,068 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-16 03:21:38
合計ジャッジ時間 2,265 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 8 ms
6,940 KB
testcase_14 AC 9 ms
6,944 KB
testcase_15 AC 9 ms
6,940 KB
testcase_16 AC 7 ms
6,940 KB
testcase_17 AC 8 ms
6,940 KB
testcase_18 AC 18 ms
6,940 KB
testcase_19 AC 19 ms
6,944 KB
testcase_20 AC 28 ms
6,940 KB
testcase_21 AC 47 ms
6,940 KB
testcase_22 AC 57 ms
6,944 KB
testcase_23 AC 65 ms
6,944 KB
testcase_24 AC 57 ms
6,940 KB
testcase_25 AC 67 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local n = io.read("*n")
local parent = {}
for i = 1, n do parent[i] = i end

local function uf_findroot(idx)
  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 lc = {}
for i = 1, n do lc[i] = 0 end
for i = 1, n - 1 do
  local a, b = io.read("*n", "*n")
  a, b = a + 1, b + 1
  lc[a] = lc[a] + 1
  lc[b] = lc[b] + 1
  local ap, bp = uf_findroot(a), uf_findroot(b)
  if ap ~= bp then
    parent[bp], parent[b] = ap, ap
  end
end

local pmap = {}
for i = 1, n do
  local p = uf_findroot(i)
  if pmap[p] then pmap[p] = pmap[p] + 1
  else pmap[p] = 1
  end
end
local minsize, minp = 1000000007, 1000000007
local mmi = math.min
local groupcnt = 0
for p, c in pairs(pmap) do
  groupcnt = groupcnt + 1
  if c < minsize then
    minsize = c
    minp = p
  end
end
local f = true
if groupcnt == 1 then
  f = true
elseif groupcnt == 2 then
  if minsize == 1 then
    f = true
    for i = 1, n do
      if uf_findroot(i) ~= minp and lc[i] == 1 then
        f = false break
      end
    end
  else
    f = false
  end
else
  f = false
end
print(f and "Bob" or "Alice")
0