結果

問題 No.1612 I hate Construct a Palindrome
ユーザー gew1fw
提出日時 2025-06-12 21:29:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,706 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 341,340 KB
最終ジャッジ日時 2025-06-12 21:30:24
合計ジャッジ時間 12,496 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 WA * 9 TLE * 3 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    adj = [[] for _ in range(N + 1)]
    edges = []
    
    for i in range(M):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        c = data[idx]
        idx += 1
        adj[a].append((b, c, i + 1))
        adj[b].append((a, c, i + 1))
        edges.append((a, b, c))
    
    # BFS setup
    visited = [dict() for _ in range(N + 1)]
    parent = [dict() for _ in range(N + 1)]  # parent[u][(f, l)] = (prev_u, prev_f, prev_l, edge_idx)
    
    q = deque()
    
    # Enqueue all edges from 1
    for i in range(M):
        a, b, c = edges[i]
        if a == 1:
            u = b
            state = (c, c)
            if state not in visited[u]:
                visited[u][state] = True
                parent[u][state] = (None, None, None, i + 1)
                q.append((u, c, c, 1))
        elif b == 1:
            u = a
            state = (c, c)
            if state not in visited[u]:
                visited[u][state] = True
                parent[u][state] = (None, None, None, i + 1)
                q.append((u, c, c, 1))
    
    found = False
    result = []
    
    while q:
        u, f, l, length = q.popleft()
        
        if length > 2 * N:
            continue
        
        if u == N:
            if f != l:
                # Reconstruct the path
                current = (u, f, l)
                result_edges = []
                while True:
                    p = parent[current[0]].get((current[1], current[2]), None)
                    if p is None:
                        break
                    prev_u, prev_f, prev_l, edge_idx = p
                    result_edges.append(edge_idx)
                    current = (prev_u, prev_f, prev_l)
                    if prev_u is None:
                        break
                # The result_edges are in reverse order
                result_edges = result_edges[::-1]
                if len(result_edges) <= 2 * N:
                    found = True
                    result = result_edges
                    break
        
        for v, c, idx in adj[u]:
            new_l = c
            new_state = (f, new_l)
            if new_state not in visited[v]:
                visited[v][new_state] = True
                parent[v][new_state] = (u, f, l, idx)
                q.append((v, f, new_l, length + 1))
    
    if found:
        print(len(result))
        for e in result:
            print(e)
    else:
        print(-1)

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