結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-10-27 13:58:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,162 ms / 3,000 ms |
コード長 | 1,680 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 112,864 KB |
最終ジャッジ日時 | 2024-07-21 21:55:48 |
合計ジャッジ時間 | 17,560 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
class Unionfind():def __init__(self, n):self.n = nself.parents = [-1] * ndef leader (self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.leader(self.parents[x])return self.parents[x]def merge(self, x, y):x = self.leader(x)y = self.leader(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef same(self, x):return self.leader(x) == self.leader(y)def size(self, x):return -self.parents[self.leader(x)]n, m, q = map(int, input().split())s = [input() for _ in range(n)]uf = Unionfind(7 * n)graph = [[] for _ in range(n)]exist = [[s[i][j] == '1' for j in range(7)] for i in range(n)]for i in range(n):for j in range(7):if exist[i][j] and exist[i][(j + 1) % 7]:uf.merge(7 * i + j, 7 * i + (j + 1) % 7)for i in range(m):u, v = map(lambda x: int(x) - 1, input().split())for j in range(7):if exist[u][j] and exist[v][j]:uf.merge(7 * u + j, 7 * v + j)graph[u].append(v)graph[v].append(u)for _ in range(q):t, x, y = map(lambda x: int(x) - 1, input().split())if t == 0:exist[x][y] = Trueif exist[x][(y + 6) % 7]:uf.merge(7 * x + (y + 6) % 7, 7 * x + y)if exist[x][(y + 8) % 7]:uf.merge(7 * x + y, 7 * x + (y + 8) % 7)for z in graph[x]:if exist[z][y]:uf.merge(7 * x + y, 7 * z + y)else:print(uf.size(7 * x))