Submission #629672

#	Time	Username	Problem	Language	Result	Execution time	Memory
629672		54skyxenon	Mecho (IOI09_mecho)	Cpython 3	46 / 100	1099 ms	34512 KiB

mecho

# https://oj.uz/problem/view/IOI09_mecho
 
from collections import deque
 
n, s = map(int, input().split())
 
forest = []
for _ in range(n):
    forest.append(input())
 
start = None
end = None
hives = []
 
for i in range(n):
    for j in range(n):
        if forest[i][j] == 'M':
            start = (i, j)
        if forest[i][j] == 'D':
            end = (i, j)
        if forest[i][j] == 'H':
            hives.append((i, j))

def valid_square(x, y):
	return 0 <= x < n and 0 <= y < n and (forest[x][y] == 'G' or forest[x][y] == 'M')

def mecho_reached(mecho_dis, bees_dis):
    return mecho_dis // s < bees_dis

def ok(eating_time):
    bees_visited = [[False] * n for _ in range(n)]
    mecho_visited = [[False] * n for _ in range(n)]
    bees_time = [[0] * n for _ in range(n)]
    mecho_time = [[0] * n for _ in range(n)]

    Q = deque()

    # move bees
    for hive_x, hive_y in hives:
        Q.append((hive_x, hive_y))
        bees_visited[hive_x][hive_y] = True

    while Q:
        x, y = Q.popleft()

        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if valid_square(nx, ny) and not bees_visited[nx][ny]:
                bees_time[nx][ny] = bees_time[x][y] + 1    
                Q.append((nx, ny))
                bees_visited[nx][ny] = True
    
    # move Mecho
    Q.append(start)
    mecho_visited[start[0]][start[1]] = True
    if bees_time[start[0]][start[1]] <= eating_time:
        Q.popleft()
    
    while Q:
        x, y = Q.popleft()

        for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            '''
            check if mecho reaces node[x][y] before the bees by dividing the time mecho takes to reach a node by s, since mecho walks s steps at a time.
            subtract the eating time from the time taken for the bees to reach the node, because that time was used by mecho for eating
            '''
            if valid_square(nx, ny) and not mecho_visited[nx][ny] and mecho_reached(mecho_time[x][y] + 1, bees_time[nx][ny] - eating_time):
                mecho_visited[nx][ny] = True
                Q.append((nx, ny))
                mecho_time[nx][ny] = mecho_time[x][y] + 1

    # check if mecho reached a node surrounding his cave before the bees
    for nx, ny in [(end[0] + 1, end[1]), (end[0] - 1, end[1]), (end[0], end[1] + 1), (end[0], end[1] - 1)]:
        if valid_square(nx, ny) and mecho_reached(mecho_time[nx][ny], bees_time[nx][ny] - eating_time) and mecho_visited[nx][ny]:
            return True

    return False
 
def bs(lo, hi):
    if lo > hi:
        return -1

    mid = (lo + hi) // 2

    if not ok(mid):
        return bs(lo, mid - 1)
    elif mid < hi and ok(mid + 1):
        return bs(mid + 1, hi)
    else:
        return mid
 
print(bs(0, n ** 2))

• Subtask 1: 46 / 100