結果

問題 No.1266 7 Colors
ユーザー 👑 obakyanobakyan
提出日時 2021-09-12 19:21:59
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 366 ms / 3,000 ms
コード長 2,086 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 5,316 KB
実行使用メモリ 35,864 KB
最終ジャッジ日時 2023-09-06 16:20:06
合計ジャッジ時間 9,975 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 279 ms
8,904 KB
testcase_04 AC 336 ms
21,872 KB
testcase_05 AC 286 ms
9,336 KB
testcase_06 AC 356 ms
34,556 KB
testcase_07 AC 362 ms
34,976 KB
testcase_08 AC 342 ms
21,792 KB
testcase_09 AC 333 ms
20,520 KB
testcase_10 AC 321 ms
20,172 KB
testcase_11 AC 317 ms
12,656 KB
testcase_12 AC 294 ms
12,928 KB
testcase_13 AC 321 ms
19,828 KB
testcase_14 AC 280 ms
9,116 KB
testcase_15 AC 353 ms
35,316 KB
testcase_16 AC 306 ms
13,492 KB
testcase_17 AC 366 ms
34,988 KB
testcase_18 AC 237 ms
35,864 KB
testcase_19 AC 209 ms
34,812 KB
testcase_20 AC 208 ms
34,948 KB
testcase_21 AC 148 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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