結果
問題 | No.1266 7 Colors |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
local n, m, q = io.read("*n", "*n", "*n", "*l")local parent = {}local canuse = {}local size = {}for i = 1, n * 7 doparent[i] = icanuse[i] = falsesize[i] = 1endlocal function uf_findroot(idx)local idx_update = idxwhile parent[idx] ~= idx doidx = parent[idx]endwhile parent[idx_update] ~= idx doparent[idx_update], idx_update = idx, parent[idx_update]endreturn idxendlocal function uf_unite(a, b)local ra, rb = uf_findroot(a), uf_findroot(b)if ra ~= rb thensize[ra] = size[ra] + size[rb]parent[rb], parent[b] = ra, raendendlocal function encode(idx, color)return (idx - 1) * 7 + colorendfor i = 1, n dolocal s = io.read()for j = 1, 7 doif s:byte(j) == 49 thencanuse[encode(i, j)] = trueendendfor j = 1, 6 dolocal z = encode(i, j)if canuse[z] and canuse[z + 1] thenuf_unite(z, z + 1)endenddolocal y, z = encode(i, 1), encode(i, 7)if canuse[y] and canuse[z] thenuf_unite(y, z)endendendlocal edge = {}for i = 1, n doedge[i] = {}endfor i = 1, m dolocal a, b = io.read("*n", "*n")table.insert(edge[a], b)table.insert(edge[b], a)endfor a = 1, n dofor j = 1, #edge[a] dolocal b = edge[a][j]if a < b thenfor c = 1, 7 dolocal y, z = encode(a, c), encode(b, c)if canuse[y] and canuse[z] thenuf_unite(y, z)endendendendendfor iq = 1, q dolocal tp, a, c = io.read("*n", "*n", "*n")if tp == 1 thenlocal z = encode(a, c)canuse[z] = trueif 1 < c and canuse[z - 1] thenuf_unite(z, z - 1)endif c < 7 and canuse[z + 1] thenuf_unite(z, z + 1)endif c == 1 and canuse[z + 6] thenuf_unite(z, z + 6)endif c == 7 and canuse[z - 6] thenuf_unite(z, z - 6)endfor j = 1, #edge[a] dolocal b = edge[a][j]local y = encode(b, c)if canuse[y] thenuf_unite(z, y)endendelselocal r = uf_findroot(encode(a, 1))print(size[r])endend