Submission #16587795

Source Code Expand

Copy
```import sys

sys.path.append("/home/contestant/.local/lib/python3.8/site-packages")

import networkx as nx

R, C = [int(x) for x in input().split()]
grid = [list(input()) for r in range(R)]

def pack(r, c):
return r * C + c

graph = nx.Graph()
top_nodes = set()  # top half of the bipartite graph
for r in range(R):
for c in range(C):
if r + 1 < R and grid[r][c] == grid[r + 1][c] == ".":
u, v = pack(r, c), pack(r + 1, c)
if (r + c) % 2 == 0:
else:
if c + 1 < C and grid[r][c] == grid[r][c + 1] == ".":
u, v = pack(r, c), pack(r, c + 1)
if (r + c) % 2 == 0:
else:

matching = nx.bipartite.maximum_matching(graph, top_nodes=top_nodes)

count = 0
for u, v in matching.items():
if u > v:
assert matching[v] == u
r1, c1 = divmod(u, C)
r2, c2 = divmod(v, C)
if r1 == r2:
if c1 > c2:
c1, c2 = c2, c1
grid[r1][c1], grid[r2][c2] = ">", "<"
elif c1 == c2:
if r1 > r2:
r1, r2 = r2, r1
grid[r1][c1] = "v"
grid[r2][c2] = "^"
count += 1

print(count)
for row in grid:
print("".join(row))

```

#### Submission Info

Submission Time 2020-09-09 10:15:15+0900 D - Maxflow atf PyPy3 (7.3.0) 100 1480 Byte AC 1123 ms 133148 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
 AC × 1
 AC × 19
Set Name Test Cases
Sample 00-sample-01.txt
All 00-sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 830 ms 117876 KB
01-01.txt AC 808 ms 117056 KB
01-02.txt AC 813 ms 117012 KB
01-03.txt AC 811 ms 117244 KB
01-04.txt AC 820 ms 117544 KB
01-05.txt AC 822 ms 117016 KB
01-06.txt AC 812 ms 117604 KB
01-07.txt AC 999 ms 129936 KB
01-08.txt AC 830 ms 118100 KB
01-09.txt AC 816 ms 117584 KB
01-10.txt AC 829 ms 118004 KB
01-11.txt AC 827 ms 117176 KB
01-12.txt AC 1044 ms 132004 KB
01-13.txt AC 1123 ms 133148 KB
01-14.txt AC 984 ms 124960 KB
01-15.txt AC 888 ms 120120 KB
01-16.txt AC 822 ms 117140 KB
01-17.txt AC 950 ms 124160 KB
01-18.txt AC 959 ms 124156 KB