結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2023-04-28 12:18:45 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,166 bytes |
コンパイル時間 | 369 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 111,048 KB |
最終ジャッジ日時 | 2024-11-17 13:14:24 |
合計ジャッジ時間 | 15,024 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 14 |
ソースコード
import sysreadline = sys.stdin.readlineclass UnionFind(object):def __init__(self, n=1):self.par = [i for i in range(n)]self.rank = [0 for _ in range(n)]self.size = [1 for _ in range(n)]def find(self, x):if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])return self.par[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x != y:if self.rank[x] < self.rank[y]:x, y = y, xif self.rank[x] == self.rank[y]:self.rank[x] += 1self.par[y] = xself.size[x] += self.size[y]def is_same(self, x, y):return self.find(x) == self.find(y)def get_size(self, x):x = self.find(x)return self.size[x]N, M, Q = map(int, readline().split())S = []for i in range(N):s = list(readline().rstrip("\n"))s = list(map(int, s))v = 0for j in range(7):if s[j]:v += 1 << jS.append(v)G = [[] for i in range(N)]for i in range(M):u, v = map(int, readline().split())u, v = u - 1, v - 1G[u].append(v)G[v].append(u)U = UnionFind(7 * N)for u in range(N):for y in range(7):if (S[u] >> y) & 1 == 0:continueym = (y - 1) % 7if (S[u] >> ym) & 1:U.union(7 * u + y, 7 * u + ym)yp = (y + 1) % 7if (S[u] >> yp) & 1:U.union(7 * u + y, 7 * u + yp)for v in G[u]:for k in range(7):if (S[u] >> k) & 1 and (S[v] >> k) & 1:U.union(7 * u + k, 7 * v + k)for _ in range(Q):q, u, y = map(int, readline().split())u, y = u - 1, y - 1if q == 1:S[u] |= 1 << yym = (y - 1) % 7if (S[u] >> ym) & 1:U.union(7 * u + y, 7 * u + ym)yp = (y + 1) % 7if (S[u] >> yp) & 1:U.union(7 * u + y, 7 * u + yp)for v in G[u]:if (S[u] >> y) & 1 and (S[v] >> y) & 1:U.union(7 * u + y, 7 * v + y)else:print(U.get_size(0))