結果

問題 No.1266 7 Colors
コンテスト
ユーザー obakyan
提出日時 2021-09-12 19:21:59
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 409 ms / 3,000 ms
コード長 2,086 bytes
コンパイル時間 102 ms
コンパイル使用メモリ 5,376 KB
実行使用メモリ 39,424 KB
最終ジャッジ日時 2024-06-24 10:46:23
合計ジャッジ時間 8,513 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

local n, m, q = io.read("*n", "*n", "*n", "*l")
local parent = {}
local canuse = {}
local size = {}
for i = 1, n * 7 do
  parent[i] = i
  canuse[i] = false
  size[i] = 1
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 function uf_unite(a, b)
  local ra, rb = uf_findroot(a), uf_findroot(b)
  if ra ~= rb then
    size[ra] = size[ra] + size[rb]
    parent[rb], parent[b] = ra, ra
  end
end

local function encode(idx, color)
  return (idx - 1) * 7 + color
end
for i = 1, n do
  local s = io.read()
  for j = 1, 7 do
    if s:byte(j) == 49 then
      canuse[encode(i, j)] = true
    end
  end
  for j = 1, 6 do
    local z = encode(i, j)
    if canuse[z] and canuse[z + 1] then
      uf_unite(z, z + 1)
    end
  end
  do
    local y, z = encode(i, 1), encode(i, 7)
    if canuse[y] and canuse[z] then
      uf_unite(y, z)
    end
  end
end
local edge = {}
for i = 1, n do
  edge[i] = {}
end
for i = 1, m do
  local a, b = io.read("*n", "*n")
  table.insert(edge[a], b)
  table.insert(edge[b], a)
end
for a = 1, n do
  for j = 1, #edge[a] do
    local b = edge[a][j]
    if a < b then
      for c = 1, 7 do
        local y, z = encode(a, c), encode(b, c)
        if canuse[y] and canuse[z] then
          uf_unite(y, z)
        end
      end
    end
  end
end
for iq = 1, q do
  local tp, a, c = io.read("*n", "*n", "*n")
  if tp == 1 then
    local z = encode(a, c)
    canuse[z] = true
    if 1 < c and canuse[z - 1] then
      uf_unite(z, z - 1)
    end
    if c < 7 and canuse[z + 1] then
      uf_unite(z, z + 1)
    end
    if c == 1 and canuse[z + 6] then
      uf_unite(z, z + 6)
    end
    if c == 7 and canuse[z - 6] then
      uf_unite(z, z - 6)
    end
    for j = 1, #edge[a] do
      local b = edge[a][j]
      local y = encode(b, c)
      if canuse[y] then
        uf_unite(z, y)
      end
    end
  else
    local r = uf_findroot(encode(a, 1))
    print(size[r])
  end
end
0