結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー 👑 obakyan
提出日時 2020-02-15 22:59:48
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 1,216 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 6,820 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 14:08:27
合計ジャッジ時間 1,926 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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