Problem p02561 (python)

Fixed submission:
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap):
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m

    def get_edge(self, idx):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, idx, new_cap, new_flow):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0:
                continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up:
                break
            self.iter[v] += 1
        return res

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0:
                        continue
                    self.level[to] = self.level[v] + 1
                    if to == t:
                        break
                    queue.append(to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited


n,m = map(int, input().split())
s = [list(input()) for _ in range(n)]

mf = MaxFlow(n * m + 2)

start = n * m
end = n * m + 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        else:
            if (i + j) % 2 == 0:
                mf.add_edge(start, i * m + j, 1)

                for i1, j1 in d:
                    if 0 <= i + i1 < n and 0 <= j + j1 < m:
                        if s[i+i1][j+j1] == '.':
                            mf.add_edge(i * m + j, (i+i1) * m + (j+j1), 1)

            else:
                mf.add_edge(i * m + j, end, 1)

print(mf.max_flow(start, end))

for i in range(len(mf.pos)):
    s1, e1, cap, flow = mf.get_edge(i)
    if flow == 0 or s1 == start or e1 == end:
        continue
    else:
        si = s1 // m
        sj = s1 % m
        ei = e1 // m
        ej = e1 % m
        if s1 - e1 == m:
            s[si][sj] = '^'
            s[ei][ej] = 'v'
        elif e1 - s1 == m:
            s[si][sj] = 'v'
            s[ei][ej] = '^'
        elif s1 - e1 == 1:
            s[si][sj] = '<'
            s[ei][ej] = '>'
        elif e1 - s1 == 1:
            s[si][sj] = '>'
            s[ei][ej] = '<'

for i in s:
    for j in i:
        print(j, end = '')
    print()

Buggy submission (verdict: Runtime Error):
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap):
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m

    def get_edge(self, idx):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, idx, new_cap, new_flow):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0:
                continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up:
                break
            self.iter[v] += 1
        return res

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0:
                        continue
                    self.level[to] = self.level[v] + 1
                    if to == t:
                        break
                    queue.append(to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited


n,m = map(int, input().split())
s = [list(input()) for _ in range(n)]

mf = MaxFlow(n * m + 2)

start = n * m
end = n * m + 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        else:
            if (i + j) % 2 == 0:
                mf.add_edge(start, i * m + j, 1)

                for i1, j1 in d:
                    if 0 <= i + i1 < n and 0 <= j + j1 < m:
                        if s[i+i1][j+j1] == '.':
                            mf.add_edge(i * m + j, (i+i1) * m + (j+j1), 1)

            else:
                mf.add_edge(i * m + j, end, 1)

print(mf.max_flow(start, end))

for i in range(len(mf.pos)):
    s1, e1, cap, flow = mf.get_edge(i)
    if flow == 0 or s1 == start or e1 == end:
        continue
    else:
        si = s1 // n
        sj = s1 % n
        ei = e1 // n
        ej = e1 % n
        if s1 - e1 == 1:
            s[si][sj] = '<'
            s[ei][ej] = '>'
        elif e1 - s1 == 1:
            s[si][sj] = '>'
            s[ei][ej] = '<'
        elif s1 - e1 == m:
            s[si][sj] = '^'
            s[ei][ej] = 'v'
        else:
            s[si][sj] = 'v'
            s[ei][ej] = '^'

for i in s:
    for j in i:
        print(j, end = '')
    print()

Buggy submission (verdict: Runtime Error):
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap):
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m

    def get_edge(self, idx):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, idx, new_cap, new_flow):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0:
                continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up:
                break
            self.iter[v] += 1
        return res

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0:
                        continue
                    self.level[to] = self.level[v] + 1
                    if to == t:
                        break
                    queue.append(to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited


n,m = map(int, input().split())
s = [list(input()) for _ in range(n)]

mf = MaxFlow(n * m + 2)

start = n * m
end = n * m + 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        else:
            if (i + j) % 2 == 0:
                mf.add_edge(start, i * n + j, 1)

                for i1, j1 in d:
                    if 0 <= i + i1 < n and 0 <= j + j1 < m:
                        if s[i+i1][j+j1] == '.':
                            mf.add_edge(i * n + j, (i+i1) * n + (j+j1), 1)

            else:
                mf.add_edge(i * n + j, end, 1)

print(mf.max_flow(start, end))

for i in range(len(mf.pos)):
    s1, e1, cap, flow = mf.get_edge(i)
    if flow == 0 or s1 == start or e1 == end:
        continue
    else:
        si = s1 // n
        sj = s1 % n
        ei = e1 // n
        ej = e1 % n
        if s1 - e1 == 1:
            s[si][sj] = '<'
            s[ei][ej] = '>'
        elif e1 - s1 == 1:
            s[si][sj] = '>'
            s[ei][ej] = '<'
        elif s1 - e1 == m:
            s[si][sj] = '^'
            s[ei][ej] = 'v'
        else:
            s[si][sj] = 'v'
            s[ei][ej] = '^'

for i in s:
    for j in i:
        print(j, end = '')
    print()

Buggy submission (verdict: Runtime Error):
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap):
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m

    def get_edge(self, idx):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, idx, new_cap, new_flow):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0:
                continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up:
                break
            self.iter[v] += 1
        return res

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0:
                        continue
                    self.level[to] = self.level[v] + 1
                    if to == t:
                        break
                    queue.append(to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited


n,m = map(int, input().split())
s = [list(input()) for _ in range(n)]

mf = MaxFlow(n * m + 2)

start = n * m
end = n * m + 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        else:
            if (i + j) % 2 == 0:
                mf.add_edge(start, i * n + j, 1)

                for i1, j1 in d:
                    if 0 <= i + i1 < n and 0 <= j + j1 < m:
                        if s[i+i1][j+j1] == '.':
                            mf.add_edge(i * n + j, (i+i1) * n + (j+j1), 1)

            else:
                mf.add_edge(i * n + j, end, 1)

print(mf.max_flow(start, end))

for i in range(n*m+2):
    s1, e1, cap, flow = mf.get_edge(i)
    if flow == 0 or s1 == start or e1 == end:
        continue
    else:
        si = s1 // n
        sj = s1 % n
        ei = e1 // n
        ej = e1 % n
        if s1 - e1 == 1:
            s[si][sj] = '<'
            s[ei][ej] = '>'
        elif e1 - s1 == 1:
            s[si][sj] = '>'
            s[ei][ej] = '<'
        elif s1 - e1 == m:
            s[si][sj] = '^'
            s[ei][ej] = 'v'
        else:
            s[si][sj] = 'v'
            s[ei][ej] = '^'

for i in s:
    for j in i:
        print(j, end = '')
    print()

Buggy submission (verdict: Runtime Error):
from collections import deque

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap):
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m

    def get_edge(self, idx):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)

    def change_edge(self, idx, new_cap, new_flow):
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow

    def dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0:
                continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up:
                break
            self.iter[v] += 1
        return res

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0:
                        continue
                    self.level[to] = self.level[v] + 1
                    if to == t:
                        break
                    queue.append(to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f:
                    break
                flow += f
        return flow

    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited


n,m = map(int, input().split())
s = [list(input()) for _ in range(n)]

mf = MaxFlow(n * m + 2)

start = n * m
end = n * m + 1
d = [(1,0), (-1,0), (0,1), (0,-1)]

for i in range(n):
    for j in range(m):
        if s[i][j] == '#':
            continue
        else:
            if (i + j) % 2 == 0:
                mf.add_edge(start, i * n + j, 1)

                for i1, j1 in d:
                    if 0 <= i + i1 < n and 0 <= j + j1 < m:
                        if s[i+i1][j+j1] == '.':
                            mf.add_edge(i * n + j, (i+i1) * n + (j+j1), 1)

            else:
                mf.add_edge(i * n + j, end, 1)

print(mf.max_flow(start, end))

for i in range(n*m+2):
    s1, e1, cap, flow = mf.get_edge(i)
    if flow == 0 or s1 == start or e1 == end:
        continue
    else:
        print(s1, e1)
        si = s1 // n
        sj = s1 % n
        ei = e1 // n
        ej = e1 % n
        if s1 - e1 == 1:
            s[si][sj] = '<'
            s[ei][ej] = '>'
        elif e1 - s1 == 1:
            s[si][sj] = '>'
            s[ei][ej] = '<'
        elif s1 - e1 == m:
            s[si][sj] = '^'
            s[ei][ej] = 'v'
        else:
            s[si][sj] = 'v'
            s[ei][ej] = '^'

for i in s:
    for j in i:
        print(j, end = '')
    print()