結果

問題 No.867 避難経路
ユーザー lam6er
提出日時 2025-03-31 17:40:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,337 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 318,704 KB
最終ジャッジ日時 2025-03-31 17:42:47
合計ジャッジ時間 16,969 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 30 TLE * 6 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from collections import deque
def main():
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr]); ptr +=1
    W = int(input[ptr]); ptr +=1
    gx = int(input[ptr])-1; ptr +=1
    gy = int(input[ptr])-1; ptr +=1
    A = []
    for _ in range(H):
        row = list(map(int, input[ptr:ptr+W]))
        ptr += W
        A.append(row)
    
    Q = int(input[ptr]); ptr +=1
    queries = []
    for _ in range(Q):
        x = int(input[ptr])-1; ptr +=1
        y = int(input[ptr])-1; ptr +=1
        k = int(input[ptr]); ptr +=1
        queries.append((x, y, k))
    # Precompute for each cell (i, j) the list of (L, S) pairs
    # 4 directions
    dirs = [ (-1,0), (1,0), (0,-1), (0,1) ]
    # For each cell, store a list of (L, S) pairs
    # Initialize all cells with empty lists
    cells = [ [ [] for _ in range(W) ] for _ in range(H) ]
    # priority_queue will be a deque, and for BFS, perhaps use a queue of cells to process
    # Starting with the exit cell
    # exit cell's (gx, gy)
    # L=1, S=A[gx][gy]
    exit_i = gx
    exit_j = gy
    cells[exit_i][exit_j].append( (1, A[exit_i][exit_j]) )
    # BFS queue: each entry is (i, j)
    from collections import deque
    q = deque()
    q.append( (exit_i, exit_j) )
    # Visited is not needed because cells can be processed multiple times, as long as new (L, S) pairs are added
    # For processing in BFS-like order
    while q:
        i, j = q.popleft()
        # Explore neighbors
        for di, dj in dirs:
            ni = i + di
            nj = j + dj
            if 0 <= ni < H and 0 <= nj < W:
                # For each neighbor (ni, nj), we can generate new (L_new, S_new) = (L+1, S+A[ni][nj])
                # Check all existing pairs in (i,j)
                # For each existing (L, S), generate new (L+1, S + A[ni][nj])
                new_pairs = []
                for L, S in cells[i][j]:
                    L_new = L + 1
                    S_new = S + A[ni][nj]
                    new_pairs.append( (L_new, S_new) )
                # Now, merge these new_pairs into the neighbor's cells[ni][nj]
                # For each new (L_new, S_new):
                # Check if it's dominated by any existing pair in cells[ni][nj]
                # And if it can dominate some existing pairs.
                added = False
                for L_new, S_new in new_pairs:
                    # Check against existing pairs
                    # First, check if this new pair is not dominated by any existing pair
                    dominated = False
                    to_remove = []
                    for idx, (L_ex, S_ex) in enumerate(cells[ni][nj]):
                        if L_ex <= L_new and S_ex <= S_new:
                            dominated = True
                            break
                        if L_ex >= L_new and S_ex >= S_new:
                            to_remove.append(idx)
                    # Remove dominated pairs in reverse order
                    for idx in reversed(to_remove):
                        del cells[ni][nj][idx]
                    if not dominated:
                        # Now check if the new pair is not already in the list (but possibly with the same L and S)
                        # Also, remove any existing pairs with L >= L_new and S >= S_new (dominated by new pair)
                        # Now add the new pair
                        cells[ni][nj].append( (L_new, S_new) )
                        added = True
                    # After possible addition, sort the list by L, then S
                    # Sort and remove duplicates if any
                if added:
                    # Sort the cells[ni][nj] list by L, then by S
                    cells[ni][nj].sort()
                    # Remove duplicates: if same L, keep the one with smaller S
                    unique = []
                    for p in cells[ni][nj]:
                        if not unique or p[0] != unique[-1][0]:
                            unique.append(p)
                        elif p[0] == unique[-1][0] and p[1] < unique[-1][1]:
                            unique.pop()
                            unique.append(p)
                    cells[ni][nj] = unique
                    # Also, add the neighbor to the queue to process its neighbors
                    q.append( (ni, nj) )
    # Precompute convex hull for each cell
    hulls = [ [ [] for _ in range(W) ] for _ in range(H) ]
    for i in range(H):
        for j in range(W):
            # Build the convex hull for cells[i][j]
            points = cells[i][j]
            if not points:
                continue  # Should not happen as per problem constraints, but safety
            # Sort points by L, then S
            points.sort()
            # Build lower convex hull
            hull = []
            for p in points:
                L, S = p
                while len(hull) >= 2:
                    # Check if the last two points and current point form a convex turn
                    L1, S1 = hull[-2]
                    L2, S2 = hull[-1]
                    # Cross product: (L2 - L1) * (S - S2) - (L - L2) * (S2 - S1)
                    # For lower hull, we want this to be >= 0
                    cross = (L2 - L1) * (S - S2) - (L - L2) * (S2 - S1)
                    if cross <= 0:
                        # Remove hull[-1]
                        hull.pop()
                    else:
                        break
                hull.append( (L, S) )
            hulls[i][j] = hull
    # Answer queries
    for x, y, k in queries:
        if x == exit_i and y == exit_j:
            # Already at exit
            print(A[x][y] + k*k)
            continue
        hull = hulls[x][y]
        if not hull:
            # Not reachable (should not happen per problem statement)
            print(0)
            continue
        c = k * k
        # Find the optimal (L, S) in hull which minimizes c*L + S
        # Since hull is sorted by L, and the lower envelope is convex,
        # the optimal point can be found via binary search
        left = 0
        right = len(hull) - 1
        best = None
        best_val = float('inf')
        # Check edge cases
        if len(hull) == 1:
            L, S = hull[0]
            print(c * L + S)
            continue
        # Binary search
        while left <= right:
            mid = (left + right) // 2
            # Compute current value
            L_mid, S_mid = hull[mid]
            val_mid = L_mid * c + S_mid
            # Compare with next
            if mid < len(hull) -1:
                L_next, S_next = hull[mid+1]
                val_next = L_next * c + S_next
                if val_next < val_mid:
                    left = mid +1
                else:
                    right = mid -1
            else:
                right = mid -1
            # Update best
            if val_mid < best_val:
                best_val = val_mid
                best = mid
        # Final check around the left region
        for i in range(max(0, left-2), min(len(hull), left+3)):
            if i <0 or i >= len(hull):
                continue
            L, S = hull[i]
            val = L * c + S
            if val < best_val:
                best_val = val
        print(best_val)
if __name__ == '__main__':
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0