結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2019-11-01 14:33:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,029 bytes |
コンパイル時間 | 845 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 77,184 KB |
最終ジャッジ日時 | 2024-09-14 22:40:53 |
合計ジャッジ時間 | 6,652 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 WA * 33 |
ソースコード
from collections import defaultdict class Unionfind: def __init__(self, N): self.par = [-1] * N self.rank = [1] * N def root(self, x): if self.par[x] < 0: return x self.par[x] = self.root(self.par[x]) return self.par[x] def unite(self, x, y): rx, ry = self.root(x), self.root(y) if rx != ry: if self.rank[rx] >= self.rank[ry]: self.par[rx] += self.par[ry] self.par[ry] = rx if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1 else: self.par[ry] += self.par[rx] self.par[rx] = ry def is_same(self, x, y): return self.root(x) == self.root(y) def count(self, x): return -self.par[self.root(x)] N, M = map(int, input().split()) S = [input() for _ in range(N)] uf = Unionfind(N*M) for i in range(N): for j in range(M): if S[i][j] != '.': for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]: if 0<=ni<N and 0<=nj<M and S[ni][nj] != '.': uf.unite(M*i+j, M*ni+nj) group = defaultdict(dict) for i in range(N): for j in range(M): if S[i][j] == 'w': if 0 not in group[uf.root(M*i+j)]: group[uf.root(M*i+j)][0] = 1 else: group[uf.root(M*i+j)][0] += 1 elif S[i][j] == 'b': if 1 not in group[uf.root(M*i+j)]: group[uf.root(M*i+j)][1]= 1 else: group[uf.root(M*i+j)][1] += 1 for k in group: if 0 not in group[k]: group[k][0] = 0 if 1 not in group[k]: group[k][1] = 0 pair_sum = 0 w_amari = 0 b_amari = 0 for k in group: pair = min(group[k][0], group[k][1]) pair_sum += pair w_amari += group[k][0]-pair b_amari += group[k][1]-pair print(pair_sum*100+min(w_amari, b_amari)*10+abs(w_amari-b_amari))