結果

問題 No.1266 7 Colors
ユーザー kohei2019kohei2019
提出日時 2023-08-14 00:15:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,235 ms / 3,000 ms
コード長 2,422 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 214,024 KB
最終ジャッジ日時 2024-11-21 18:28:23
合計ジャッジ時間 19,057 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#unionfind
import collections
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = list(range(n))
self.size0 = [1]*(n)
self.roots = n
def find(self, x):
if self.parents[x] == x:
return x
else:
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, x
if x == y:
return
self.size0[x] += self.size0[y]
self.roots -= 1
self.parents[y] = x
def 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 ret
def rootsf(self):#O(N)
ret = []
for i in range(self.n):
if self.find(i) == i:
ret.append(i)
return ret
def group_count(self):#O(1)
return self.roots
def all_group_members(self):#O(N)
ret = collections.defaultdict(lambda:[])
for i in range(self.n):
ret[self.find(i)].append(i)
return ret
N,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 -= 1
v -= 1
lsg[u].append(v)
lsg[v].append(u)
for k in range(7):
if lsS[u][k] == '1' and lsS[v][k] == '1':
pair.append((u*7+k,v*7+k))
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 -= 1
y -= 1
if 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))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0