結果
問題 | No.1266 7 Colors |
ユーザー |
|
提出日時 | 2023-08-14 00:11:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,433 bytes |
コンパイル時間 | 459 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 214,536 KB |
最終ジャッジ日時 | 2024-11-21 18:23:31 |
合計ジャッジ時間 | 21,386 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 3 WA * 16 |
ソースコード
#unionfind経路圧縮ありimport collectionsclass UnionFind():def __init__(self, n):self.n = nself.parents = list(range(n))self.size0 = [1]*(n)self.roots = ndef find(self, x):if self.parents[x] == x:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if self.parents[x] > self.parents[y]:x, y = y, xif x == y:returnself.size0[x] += self.size0[y]self.roots -= 1self.parents[y] = xdef size(self, x):#O(1)xが含まれる集合の要素数return self.size0[self.find(x)]def same(self, x, y):#O(1)return self.find(x) == self.find(y)def membersf(self, x):#取り出し部分はO(N)p = self.find(x)ret = []for i in range(self.n):if self.find(i) == p:ret.append(i)return retdef rootsf(self):#根の要素O(N)ret = []for i in range(self.n):if self.find(i) == i:ret.append(i)return retdef group_count(self):#根の数O(1)return self.rootsdef all_group_members(self):#O(N)ret = collections.defaultdict(lambda:[])for i in range(self.n):ret[self.find(i)].append(i)return retN,M,Q = map(int,input().split())lsS = [list(input()) for i in range(N)]lsg = [[] for i in range(N)]pair = []for i in range(N):for j in range(7):if lsS[i][j] == '1' and lsS[i][(j+1)%7] == '1':pair.append((i*7+j,i*7+(j+1)%7))for i in range(M):u,v = map(int,input().split())u -= 1v -= 1lsg[u].append(v)lsg[v].append(u)for i in range(7):if lsS[u][i] == '1' and lsS[v][i] == '1':pair.append((u*7+i,v*7+i))UF = UnionFind(7*N)for x,y in pair:UF.union(x, y)for _ in range(Q):q,x,y = map(int,input().split())x -= 1y -= 1if q == 1:lsS[x][y] == '1'if lsS[x][(y-1)%7] == '1':UF.union(x*7+y, x*7+(y-1)%7)if lsS[x][(y+1)%7] == '1':UF.union(x*7+y, x*7+(y+1)%7)for g in lsg[x]:if lsS[g][y]=='1':UF.union(x*7+y, g*7+y)else:print(UF.size(x*7))