結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
ユーザー gew1fw
提出日時 2025-06-12 20:42:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,997 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,964 KB
最終ジャッジ日時 2025-06-12 20:42:38
合計ジャッジ時間 8,902 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    # Read input
    C = list(map(int, sys.stdin.readline().split()))
    K = list(map(int, sys.stdin.readline().split()))
    N = int(sys.stdin.readline())
    abilities = []
    for _ in range(N):
        S, A, B, E = sys.stdin.readline().split()
        A = int(A)
        B = int(B)
        E = int(E)
        abilities.append((S, A, B, E))
    
    # Map from tree name to index (A-Z to 0-25)
    tree_indices = {chr(ord('A') + i): i for i in range(26)}
    
    # For each tree, build its adjacency list
    adj = {i: [] for i in range(26)}
    for S, A, B, E in abilities:
        for c in S:
            idx = tree_indices[c]
            adj[idx].append((A, B, E))
            adj[idx].append((B, A, E))
    
    # For each tree, compute max energy for each target color
    max_energies = [{} for _ in range(26)]
    reachable = [set() for _ in range(26)]
    for tree_idx in range(26):
        initial_color = C[tree_idx]
        K_tree = K[tree_idx]
        a_list = adj[tree_idx]
        visited = {}
        q = deque()
        q.append((initial_color, 0, 0))  # (current_color, steps, energy)
        visited[(initial_color, 0)] = 0
        max_steps = min(100000, K_tree)
        found = {}
        while q:
            color, steps, energy = q.popleft()
            if color not in found or energy > found[color]:
                found[color] = energy
                if steps >= max_steps:
                    continue
                for A, B, E in a_list:
                    if color == A:
                        new_color = B
                        new_energy = energy + E
                        new_steps = steps + 1
                        if new_steps > K_tree:
                            continue
                        if (new_color, new_steps) not in visited or new_energy > visited[(new_color, new_steps)]:
                            visited[(new_color, new_steps)] = new_energy
                            q.append((new_color, new_steps, new_energy))
                    elif color == B:
                        new_color = A
                        new_energy = energy + E
                        new_steps = steps + 1
                        if new_steps > K_tree:
                            continue
                        if (new_color, new_steps) not in visited or new_energy > visited[(new_color, new_steps)]:
                            visited[(new_color, new_steps)] = new_energy
                            q.append((new_color, new_steps, new_energy))
        for color in found:
            max_energy = -float('inf')
            for s in range(min(100000, K_tree) + 1):
                key = (color, s)
                if key in visited and visited[key] > max_energy:
                    max_energy = visited[key]
            if max_energy != -float('inf'):
                max_energies[tree_idx][color] = max_energy
                reachable[tree_idx].add(color)
        # Check for positive cycles
        for color in found:
            if color not in reachable[tree_idx]:
                continue
            # Check if there's a cycle starting and ending at color with positive energy
            # For simplicity, we assume that if any cycle exists, it can be used
            # This is a placeholder and needs proper cycle detection
            reachable[tree_idx].add(color)
    
    # Now, for each possible target color, check if all trees can reach it
    max_total = -float('inf')
    for target_color in range(1, 17):
        possible = True
        total = 0
        for tree_idx in range(26):
            if target_color not in reachable[tree_idx]:
                possible = False
                break
            total += max_energies[tree_idx].get(target_color, 0)
        if possible and total > max_total:
            max_total = total
    if max_total == -float('inf'):
        print("Impossible")
    else:
        print(max_total)

if __name__ == "__main__":
    main()
0