結果
| 問題 |
No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-09 21:00:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,074 bytes |
| コンパイル時間 | 234 ms |
| コンパイル使用メモリ | 82,412 KB |
| 実行使用メモリ | 79,808 KB |
| 最終ジャッジ日時 | 2025-04-09 21:01:08 |
| 合計ジャッジ時間 | 8,766 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 8 WA * 6 TLE * 1 -- * 27 |
ソースコード
import sys
from collections import defaultdict, deque
def main():
C = list(map(int, sys.stdin.readline().split()))
K = list(map(int, sys.stdin.readline().split()))
N = int(sys.stdin.readline())
operations = []
for _ in range(N):
S, A, B, E = sys.stdin.readline().split()
A = int(A)
B = int(B)
E = int(E)
operations.append((S, A, B, E))
# Preprocess for each alpha (A-Z) which operations apply to it
alpha_operations = [[] for _ in range(26)]
for op in operations:
S, A, B, E = op
present = [False]*26
for c in S:
idx = ord(c) - ord('A')
present[idx] = True
for i in range(26):
if present[i]:
alpha_operations[i].append((A, B, E))
max_total = -float('inf')
possible_targets = []
for target in range(1, 17):
valid = True
total = 0
for alpha in range(26):
k_alpha = K[alpha]
initial_color = C[alpha]
if k_alpha == 0:
if initial_color != target:
valid = False
break
continue
# Check if target is reachable from initial_color for this alpha
# Build the transition graph
graph = defaultdict(list) # color -> list of (next_color, energy)
for A_i, B_i, E_i in alpha_operations[alpha]:
graph[A_i].append((B_i, E_i))
graph[B_i].append((A_i, E_i))
# Check reachability using BFS
visited = set()
queue = deque([(initial_color, 0)])
found = False
min_steps = None
max_energy = -float('inf')
steps_energy = {}
visited_steps = defaultdict(dict) # color: { steps: max_energy }
if initial_color == target:
found = True
min_steps = 0
max_energy = 0
while queue and not found:
color, steps = queue.popleft()
if steps > 1000:
break
if color == target and steps > 0:
found = True
min_steps = steps
break
if steps > k_alpha:
continue
for next_color, energy in graph.get(color, []):
new_steps = steps + 1
new_energy = (steps_energy.get(color, {}).get(steps, 0)) + energy
if next_color not in visited_steps or new_steps not in visited_steps[next_color] or visited_steps[next_color][new_steps] < new_energy:
if new_steps not in visited_steps[next_color]:
visited_steps[next_color][new_steps] = new_energy
else:
if visited_steps[next_color][new_steps] >= new_energy:
continue
visited_steps[next_color][new_steps] = new_energy
queue.append((next_color, new_steps))
if next_color == target and (min_steps is None or new_steps < min_steps):
min_steps = new_steps
if initial_color == target:
found = True
min_steps = 0
max_energy = 0
if not found:
valid = False
break
# Compute cycle_avg using Karp's algorithm on the graph for this alpha, starting from target
# Build adjacency list for this alpha
adj = defaultdict(list)
for A_i, B_i, E in alpha_operations[alpha]:
adj[A_i].append((B_i, E))
adj[B_i].append((A_i, E))
# Maximum mean cycle starting and ending at target
nodes = set()
for u in adj:
nodes.add(u)
nodes = list(nodes)
if not adj.get(target, []):
cycle_avg = -float('inf')
else:
# Karp's algorithm for max mean cycle
INF = -float('inf')
max_len = 100
F = [[INF]* (max_len+1) for _ in range(17)]
F[target][0] = 0
for m in range(1, max_len+1):
for u in nodes:
for v, e in adj[u]:
if F[u][m-1] != INF:
if F[v][m] < F[u][m-1] + e:
F[v][m] = F[u][m-1] + e
max_mean = -float('inf')
for m in range(1, max_len+1):
for u in adj:
if F[u][m] == INF:
continue
for v, e in adj[u]:
if v == target and m+1 <= max_len:
total_e = F[u][m] + e
if total_e == INF:
continue
if m+1 >0:
mean = total_e / (m+1)
if mean > max_mean:
max_mean = mean
cycle_avg = max_mean if max_mean != -float('inf') else -float('inf')
if cycle_avg > 0:
pass
else:
cycle_avg = -float('inf')
if cycle_avg > 0:
max_possible = max_energy + (k_alpha - min_steps)*cycle_avg
else:
max_possible = max_energy
total += max_possible
if valid:
possible_targets.append(total)
if not possible_targets:
print("Impossible")
else:
max_total = max(possible_targets)
print(max_total)
if __name__ == "__main__":
main()