結果

問題 No.2328 Build Walls
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:53:50
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,175 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 852,360 KB
最終ジャッジ日時 2025-04-16 00:55:51
合計ジャッジ時間 5,817 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    ptr = 0
    H = int(data[ptr])
    ptr += 1
    W = int(data[ptr])
    ptr += 1

    A_rows = []
    for _ in range(H-2):
        row = list(map(int, data[ptr:ptr+W]))
        ptr += W
        A_rows.append(row)

    INF = 1 << 60

    def get_in_id(i, j):
        return (i-1) * W * 2 + (j-1) * 2

    def get_out_id(i, j):
        return get_in_id(i, j) + 1

    S = H * W * 2
    T = S + 1
    size = T + 1

    graph = [[] for _ in range(size)]

    for i in range(1, H+1):
        for j in range(1, W+1):
            in_id = get_in_id(i, j)
            out_id = get_out_id(i, j)
            if i == 1 or i == H:
                cap = INF
            else:
                a = A_rows[i-2][j-1]
                if a == -1:
                    cap = INF
                else:
                    cap = a
            graph[in_id].append((out_id, len(graph[out_id]), cap))
            graph[out_id].append((in_id, len(graph[in_id])-1, 0))

            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni = i + di
                nj = j + dj
                if 1 <= ni <= H and 1 <= nj <= W:
                    neighbor_in_id = get_in_id(ni, nj)
                    graph[out_id].append((neighbor_in_id, len(graph[neighbor_in_id]), INF))
                    graph[neighbor_in_id].append((out_id, len(graph[out_id])-1, 0))

                    neighbor_out_id = get_out_id(ni, nj)
                    graph[neighbor_out_id].append((in_id, len(graph[in_id]), INF))
                    graph[in_id].append((neighbor_out_id, len(graph[neighbor_out_id])-1, 0))

    for j in range(1, W+1):
        in_id = get_in_id(1, j)
        graph[S].append((in_id, len(graph[in_id]), INF))
        graph[in_id].append((S, len(graph[S])-1, 0))

    for j in range(1, W+1):
        out_id = get_out_id(H, j)
        graph[out_id].append((T, len(graph[T]), INF))
        graph[T].append((out_id, len(graph[out_id])-1, 0))

    def max_flow(s, t):
        flow = 0
        while True:
            level = [-1] * size
            q = deque()
            q.append(s)
            level[s] = 0
            while q:
                v = q.popleft()
                for edge in graph[v]:
                    to, rev, cap = edge
                    if cap > 0 and level[to] == -1:
                        level[to] = level[v] + 1
                        q.append(to)
                        if to == t:
                            break
            if level[t] == -1:
                return flow
            ptr = [0] * size
            while True:
                stack = [(s, INF)]
                found = False
                while stack:
                    v, upTo = stack[-1]
                    if v == t:
                        found = True
                        break
                    while ptr[v] < len(graph[v]):
                        to, rev, cap = graph[v][ptr[v]]
                        if cap > 0 and level[v] < level[to]:
                            stack.append((to, min(upTo, cap)))
                            break
                        ptr[v] += 1
                    else:
                        stack.pop()
                        if stack:
                            ptr[stack[-1][0]] += 1
                if not found:
                    break
                min_flow = upTo
                for i in range(1, len(stack)):
                    v = stack[i-1][0]
                    to = stack[i][0]
                    for edge in graph[v]:
                        if edge[0] == to and edge[2] > 0:
                            edge_idx = ptr[v]
                            graph[v][edge_idx] = (to, edge[1], edge[2] - min_flow)
                            rev_edge = graph[to][edge[1]]
                            graph[to][edge[1]] = (v, rev_edge[1], rev_edge[2] + min_flow)
                            break
                flow += min_flow
                if flow >= INF:
                    return INF
        return flow

    mf = max_flow(S, T)
    if mf >= INF:
        print(-1)
    else:
        print(mf)

if __name__ == "__main__":
    main()
0