結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    # Read input
    input = sys.stdin.read().split()
    ptr = 0

    # Read C_alpha for each tree A-Z
    C = [0] * 26
    for i in range(26):
        C[i] = int(input[ptr])
        ptr += 1

    # Read K_alpha for each tree A-Z
    K = [0] * 26
    for i in range(26):
        K[i] = int(input[ptr])
        ptr += 1

    # Read N
    N = int(input[ptr])
    ptr += 1

    # Read each ability
    abilities = []
    for _ in range(N):
        S = input[ptr]
        A = int(input[ptr+1])
        B = int(input[ptr+2])
        E = int(input[ptr+3])
        ptr +=4
        abilities.append( (S, A, B, E) )

    # For each tree, precompute applicable abilities
    tree_abilities = [[] for _ in range(26)]  # A-Z
    for i in range(N):
        S, A, B, E = abilities[i]
        for c in S:
            idx = ord(c) - ord('A')
            tree_abilities[idx].append( (A, B, E) )

    max_total = -float('inf')
    possible = False

    # For each possible target color T
    for T in range(1, 17):
        total = 0
        possible_T = True

        for alpha in range(26):
            initial_color = C[alpha]
            max_steps = K[alpha]
            if max_steps == 0:
                # Can't change color
                if initial_color != T:
                    possible_T = False
                    break
                else:
                    continue

            # Build the graph for this tree
            graph = [[] for _ in range(17)]  # colors are 1-16
            for a, b, e in tree_abilities[alpha]:
                graph[a].append( (b, e) )
                graph[b].append( (a, e) )

            # BFS to find all possible paths
            # Use DP: for each color, track the max E and steps
            dp = [{} for _ in range(17)]  # color to (steps: max E)
            queue = deque()

            # Start state: initial_color, 0 steps, 0 E
            dp[initial_color][0] = 0
            queue.append( (initial_color, 0) )

            max_E = -float('inf')

            while queue:
                current_color, steps = queue.popleft()
                current_E = dp[current_color][steps]

                if current_color == T:
                    if steps <= max_steps:
                        if current_E > max_E:
                            max_E = current_E

                if steps >= max_steps:
                    continue

                for neighbor, e in graph[current_color]:
                    new_steps = steps + 1
                    new_E = current_E + e
                    if new_steps > max_steps:
                        continue
                    if new_steps in dp[neighbor]:
                        if new_E > dp[neighbor][new_steps]:
                            dp[neighbor][new_steps] = new_E
                            queue.append( (neighbor, new_steps) )
                    else:
                        dp[neighbor][new_steps] = new_E
                        queue.append( (neighbor, new_steps) )

            # Also need to check if after some steps, we can get to T and then loop a cycle
            # This requires finding a cycle with positive gain
            has_cycle = False
            cycle_gain = 0
            cycle_length = 0

            # To find cycles, look for any path that starts and ends at T
            # So perform BFS from T and see if we can return to T with positive E
            cycle_queue = deque()
            cycle_queue.append( (T, 0, 0) )  # (current_color, steps, E)
            visited = set()
            max_cycle_gain = -float('inf')
            max_cycle_length = 0

            while cycle_queue:
                color, steps, e = cycle_queue.popleft()
                if color == T and steps != 0:
                    if e > max_cycle_gain:
                        max_cycle_gain = e
                        max_cycle_length = steps
                if steps > 100:  # prevent infinite loops
                    break
                for neighbor, e_step in graph[color]:
                    new_steps = steps + 1
                    new_e = e + e_step
                    if (neighbor, new_steps) not in visited:
                        visited.add( (neighbor, new_steps) )
                        cycle_queue.append( (neighbor, new_steps, new_e) )

            if max_cycle_gain > 0:
                # Can loop this cycle
                steps_used = 0
                for s in range(max_steps + 1):
                    if s in dp[T]:
                        current_E = dp[T][s]
                        remaining = max_steps - s
                        num_cycles = remaining // max_cycle_length
                        total_E = current_E + num_cycles * max_cycle_gain
                        if total_E > max_E:
                            max_E = total_E

            if max_E == -float('inf'):
                possible_T = False
                break

            total += max_E

        if possible_T:
            possible = True
            if total > max_total:
                max_total = total

    if possible:
        print(max_total)
    else:
        print("Impossible")

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