Submission #549431

#	Time	Username	Problem	Language	Result	Execution time	Memory
549431		beaconmc	Mecho (IOI09_mecho)	Pypy 3	56 / 100	788 ms	65536 KiB

mecho

from collections import *
n,s = map(int, input().split())
grid = [list(input()) for i in range(n)]

hives = []
start = []
end = []
for i in range(n):
    for j in range(n):
        if grid[i][j] == "M":
            start = [i,j]
        elif grid[i][j] == "D":
            end = [i,j]
        elif grid[i][j] == "H":
            hives.append([i,j])
            grid[i][j] = 0
def bfsinit():           
    d = deque()
    for i in hives:
        d.append(i+[0])
    while len(d):
        node = d.popleft()

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n:
                if grid[a][b] == "G" or grid[a][b] == "M":
                    d.append([a,b,node[2]+1])
                    grid[a][b] = node[2]+1
visited = [[False for i in range(n)] for i in range(n)]

def test(time):
    d = deque()
    if grid[start[0]][start[1]] <= time:
        return False
    for i in range(n):
        for j in range(n):
            visited[i][j] = False
    d.append(start+[0])
    while len(d):
        node = d.popleft()
        if node[0] == end[0] and node[1]==end[1]:
            return True

        for a,b in [(0,1), (0,-1), (1, 0), (-1, 0)]:
            a += node[0]
            b += node[1]
            if 0<=a<n and 0<=b<n and not visited[a][b]:
                if grid[a][b]=="T":
                    continue
                if grid[a][b] == "D" or int(grid[a][b]) > time+(node[2]+1)//s:
                    d.append([a,b,node[2]+1])
                    visited[a][b] = True
    return False
    
bfsinit()


lo = -1
hi = n*n

while lo<hi:
    mid = lo+(hi-lo+1)//2
    if test(mid):
        lo = mid
    else:
        hi = mid-1
print(lo)

• Subtask 1: 56 / 100