結果
問題 | No.1266 7 Colors |
ユーザー |
![]() |
提出日時 | 2020-10-24 00:10:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,334 bytes |
コンパイル時間 | 113 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 66,560 KB |
最終ジャッジ日時 | 2024-07-21 14:07:18 |
合計ジャッジ時間 | 25,526 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 14 |
ソースコード
import sysclass UnionFind:def __init__(self, N):self.p = list(range(N))self.rank = [0] * Nself.size = [1] * Ndef root(self, x):if self.p[x] != x:self.p[x] = self.root(self.p[x])return self.p[x]def same(self, x, y):return self.root(x) == self.root(y)def unite(self, x, y):u = self.root(x)v = self.root(y)if u == v:returnif self.rank[u] < self.rank[v]:self.p[u] = vself.size[v] += self.size[u]self.size[u] = 0else:self.p[v] = uself.size[u] += self.size[v]self.size[v] = 0if self.rank[u] == self.rank[v]:self.rank[u] += 1def count(self, x):return self.size[self.root(x)]def main():input = sys.stdin.buffer.readlineN, M, Q = map(int, input().split())S = [int(input(), 2) for _ in range(N)]G = [[] for _ in range(N)]for i in range(M):u, v = map(int, input().split())u -= 1v -= 1G[u].append(v)G[v].append(u)uf = UnionFind(7 * N)for v, s in enumerate(S):ones = [i for i in range(7) if s>>(6-i)&1]v_offset = 7 * vif len(ones) >= 2:for o1, o2 in zip(ones, ones[1:]):if o1 + 1 == o2:uf.unite(v_offset+o1, v_offset+o2)if ones[0] == 0 and ones[-1] == 6:uf.unite(v_offset, v_offset+6)for u in G[v]:for o in ones:if S[u]>>(6-o)&1:uf.unite(v_offset+o, u*7+o)Ans = []for _ in range(Q):t, x, y = map(int, input().split())x -= 1if t == 1:v_offset = x * 7d = 7-yS[x] |= 1 << dv = v_offset + (y-1)d2 = (d-1)%7if S[x] >> d2 & 1:uf.unite(v, v_offset+y%7)d2 = (d+1)%7if S[x] >> d2 & 1:uf.unite(v, v_offset+(y-2)%7)for u in G[x]:if S[u]>>d&1:u = u * 7 + y-1uf.unite(v, u)else:ans = uf.count(0)Ans.append(ans)print("\n".join(map(str, Ans)))main()