結果
問題 | 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 defaultdictclass Unionfind:def __init__(self, N):self.par = [-1] * Nself.rank = [1] * Ndef root(self, x):if self.par[x] < 0:return xself.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] = rxif self.rank[rx] == self.rank[ry]:self.rank[rx] += 1else:self.par[ry] += self.par[rx]self.par[rx] = rydef 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] = 1else:group[uf.root(M*i+j)][0] += 1elif S[i][j] == 'b':if 1 not in group[uf.root(M*i+j)]:group[uf.root(M*i+j)][1]= 1else:group[uf.root(M*i+j)][1] += 1for k in group:if 0 not in group[k]:group[k][0] = 0if 1 not in group[k]:group[k][1] = 0pair_sum = 0w_amari = 0b_amari = 0for k in group:pair = min(group[k][0], group[k][1])pair_sum += pairw_amari += group[k][0]-pairb_amari += group[k][1]-pairprint(pair_sum*100+min(w_amari, b_amari)*10+abs(w_amari-b_amari))