結果

問題 No.1266 7 Colors
ユーザー 👑 obakyanobakyan
提出日時 2021-09-12 19:21:59
言語 Lua
(LuaJit 2.1.1696795921)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 281 ms
9,856 KB
testcase_04 AC 365 ms
24,576 KB
testcase_05 AC 279 ms
10,240 KB
testcase_06 AC 396 ms
37,760 KB
testcase_07 AC 403 ms
38,528 KB
testcase_08 AC 359 ms
24,832 KB
testcase_09 AC 365 ms
22,656 KB
testcase_10 AC 353 ms
22,016 KB
testcase_11 AC 296 ms
13,952 KB
testcase_12 AC 323 ms
14,336 KB
testcase_13 AC 331 ms
21,376 KB
testcase_14 AC 279 ms
10,240 KB
testcase_15 AC 404 ms
38,784 KB
testcase_16 AC 321 ms
14,720 KB
testcase_17 AC 409 ms
38,400 KB
testcase_18 AC 228 ms
39,424 KB
testcase_19 AC 229 ms
38,400 KB
testcase_20 AC 223 ms
38,400 KB
testcase_21 AC 112 ms
5,376 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