#681096 (Python3) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	vwxyz
提出日時	2021-07-22 21:05:13
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	87 ms / 2,000 ms
コード長	5,708 bytes
コンパイル時間	107 ms
コンパイル使用メモリ	13,184 KB
実行使用メモリ	15,232 KB
最終ジャッジ日時	2024-09-23 07:32:15
合計ジャッジ時間	5,784 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	50 ms 13,312 KB
testcase_01	AC	64 ms 13,824 KB
testcase_02	AC	54 ms 13,312 KB
testcase_03	AC	50 ms 12,928 KB
testcase_04	AC	52 ms 13,184 KB
testcase_05	AC	53 ms 13,056 KB
testcase_06	AC	50 ms 13,056 KB
testcase_07	AC	58 ms 13,568 KB
testcase_08	AC	53 ms 13,440 KB
testcase_09	AC	51 ms 13,312 KB
testcase_10	AC	51 ms 13,056 KB
testcase_11	AC	58 ms 13,440 KB
testcase_12	AC	48 ms 12,928 KB
testcase_13	AC	48 ms 12,928 KB
testcase_14	AC	48 ms 12,928 KB
testcase_15	AC	47 ms 13,056 KB
testcase_16	AC	72 ms 14,336 KB
testcase_17	AC	75 ms 14,336 KB
testcase_18	AC	76 ms 14,464 KB
testcase_19	AC	48 ms 12,800 KB
testcase_20	AC	65 ms 14,080 KB
testcase_21	AC	71 ms 14,080 KB
testcase_22	AC	59 ms 13,696 KB
testcase_23	AC	48 ms 12,928 KB
testcase_24	AC	48 ms 13,056 KB
testcase_25	AC	48 ms 12,928 KB
testcase_26	AC	48 ms 12,928 KB
testcase_27	AC	49 ms 12,928 KB
testcase_28	AC	60 ms 13,952 KB
testcase_29	AC	64 ms 14,208 KB
testcase_30	AC	64 ms 13,952 KB
testcase_31	AC	78 ms 15,232 KB
testcase_32	AC	62 ms 13,824 KB
testcase_33	AC	63 ms 14,080 KB
testcase_34	AC	52 ms 13,312 KB
testcase_35	AC	52 ms 13,312 KB
testcase_36	AC	60 ms 13,568 KB
testcase_37	AC	77 ms 14,336 KB
testcase_38	AC	87 ms 14,336 KB
testcase_39	AC	57 ms 13,440 KB
testcase_40	AC	65 ms 13,824 KB
testcase_41	AC	53 ms 13,312 KB
testcase_42	AC	55 ms 13,312 KB
testcase_43	AC	56 ms 13,568 KB
testcase_44	AC	70 ms 14,080 KB
testcase_45	AC	52 ms 13,312 KB
testcase_46	AC	54 ms 13,184 KB
testcase_47	AC	64 ms 13,952 KB
testcase_48	AC	75 ms 14,720 KB
testcase_49	AC	56 ms 13,440 KB
testcase_50	AC	53 ms 13,312 KB
testcase_51	AC	73 ms 14,336 KB
testcase_52	AC	59 ms 13,696 KB
testcase_53	AC	52 ms 13,312 KB
testcase_54	AC	55 ms 13,440 KB
testcase_55	AC	52 ms 13,184 KB
testcase_56	AC	51 ms 13,312 KB
testcase_57	AC	53 ms 13,184 KB
testcase_58	AC	63 ms 13,952 KB
testcase_59	AC	54 ms 13,440 KB
testcase_60	AC	86 ms 14,720 KB
testcase_61	AC	81 ms 14,720 KB
testcase_62	AC	49 ms 12,928 KB
testcase_63	AC	48 ms 13,056 KB
testcase_64	AC	52 ms 13,312 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
from typing import NamedTuple, Optional, List, cast

class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int
 
    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None
 
    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []
 
    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m
 
    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MFGraph._Edge, e.rev)
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )
 
    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]
 
    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        assert e.rev is not None
        e.rev.cap = new_flow
 
    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))
 
        current_edge = [0] * self._n
        level = [0] * self._n
 
        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value
 
        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False
 
        def dfs(lim: int) -> int:
            stack = []
            edge_stack: List[MFGraph._Edge] = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        assert e.rev is not None
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = cast(MFGraph._Edge, e.rev)
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0
 
        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow
 
    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited

N,M=map(int,readline().split())
S=[readline().rstrip() for i in range(N)]
MFG=MFGraph(N*M+2)
s=0
t=N*M+1
cntw=0
cntb=0
for i in range(N):
    for j in range(M):
        if S[i][j]=='w':
            MFG.add_edge(0,i*M+j+1,1)
            cntw+=1
            for di,dj in ((0,1),(1,0),(0,-1),(-1,0)):
                if 0<=i+di<=N-1 and 0<=j+dj<=M-1 and S[i+di][j+dj]=='b':
                    MFG.add_edge(i*M+j+1,(i+di)*M+j+dj+1,1)
        if S[i][j]=='b':
            MFG.add_edge(i*M+j+1,t,1)
            cntb+=1
ans=cntb+cntw+min(cntw,cntb)*8+MFG.flow(s,t)*90
print(ans)

yukicoder

結果

テストケース

ソースコード