#882455 (PyPy3) No.421 しろくろチョコレート

• 問題: No.421 しろくろチョコレート
• ユーザー: Navier_Boltzmann
• 提出日時: 2023-06-17 14:07:58
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 2,560 bytes
• コンパイル時間: 172 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 78,208 KB
• 最終ジャッジ日時: 2024-06-25 04:48:05
• 合計ジャッジ時間: 6,860 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 32 WA * 33

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
from collections import *
from itertools import *
from functools import *
from heapq import *
import sys,math
input = sys.stdin.readline
class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n
        self.member = [[i] for i in range(n)]
    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        for tmp in self.member[y]:
            self.member[x].append(tmp)
        self.parent_or_size[y] = x
        return x
        
    def members(self,a):
        
        return self.member[self.leader(a)]
    
    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)
    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]
N,M = map(int,input().split())
S = [list(input())[:-1] for _ in range(N)]
H,W = N,M
if H>W:
    H,W = W,H
    S = list(zip(*S))
def nb(x,y):
    tmp = []
    if x+1<H:
        tmp.append((x+1,y))
    if x-1>=0:
        tmp.append((x-1,y))
    if y+1<W:
        tmp.append((x,y+1))
    if y-1>=0:
        tmp.append((x,y-1))
    return tmp
    
D = DSU(N*M)
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            continue
        
        for ix,iy in nb(i,j):
            if S[ix][iy]!='.':
                D.merge(W*ix + iy,W*i+j)
C = Counter([])
ans = 0
for g in D.groups():
    
    i,j = divmod(g[0],W)
    if S[i][j]=='.':
        continue
    
    b = 0
    w = 0
    for i in g:
        ix,iy = divmod(i,W)
        if S[ix][iy]=='w':
            w += 1
        else:
            b += 1
    if b==w:
        ans += b*100
    elif b>w:
        ans += w*100
        C['b'] += b-w
    else:
        b,w = w,b
        ans += w*100
        C['w'] += b-w
a,b = C['b'],C['w']
M = max(a,b)
m = min(a,b)
ans += 10*m
ans += (M-m)
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX