結果

問題 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
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0