Submission #1177553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177553		aditya_k47	Mecho (IOI09_mecho)	Pypy 3	31 / 100	578 ms	131072 KiB

mecho

from collections import deque

def is_reachable_with_waiting_time(wait_time, n, s, L, dp_bees, start, end):
    dp = [[float("inf")] * n for _ in range(n)]
    dp[start[0]][start[1]] = 0
    
    q = deque([start])
    while q:
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and L[nx][ny] not in "TH":
                new_time = dp[x][y] + 1
                if new_time < dp[nx][ny] and (new_time / s) < dp_bees[nx][ny] - wait_time:
                    dp[nx][ny] = new_time
                    q.append((nx, ny))
    
    return dp[end[0]][end[1]] != float("inf")

def max_waiting_time(n, s, L):
    dp_bees = [[float("inf")] * n for _ in range(n)]
    bees, start, end = [], (-1, -1), (-1, -1)
    
    # Identify positions of bees, start, and end
    for i in range(n):
        for j in range(n):
            if L[i][j] == "H":
                bees.append((i, j))
                dp_bees[i][j] = 0
            elif L[i][j] == "M":
                start = (i, j)
            elif L[i][j] == "D":
                end = (i, j)
    
    # BFS to compute minimum time for bees to reach each tile
    q = deque(bees)
    while q:
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and dp_bees[nx][ny] > dp_bees[x][y] + 1 and L[nx][ny] != "T":
                dp_bees[nx][ny] = dp_bees[x][y] + 1
                q.append((nx, ny))
    
    # Binary search for the maximum waiting time
    low, high, ans = 0, n * n, -1
    while low <= high:
        mid = (low + high) // 2
        if is_reachable_with_waiting_time(mid, n, s, L, dp_bees, start, end):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    
    return ans

# Read input
def main():
    n, s = map(int, input().split())
    L = [input().strip() for _ in range(n)]
    print(max_waiting_time(n, s, L))

if __name__ == "__main__":
    main()

Compilation message (stdout)

Compiling 'mecho.py'...

=======
  adding: __main__.pyc (deflated 47%)

=======

• Subtask 1: 31 / 100