結果

問題 No.1612 I hate Construct a Palindrome
ユーザー lam6er
提出日時 2025-03-31 17:44:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,907 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 174,000 KB
最終ジャッジ日時 2025-03-31 17:45:01
合計ジャッジ時間 9,151 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx +=1

    edges = []
    adj = [[] for _ in range(N+1)]  # nodes are 1-based
    for edge_id in range(1, M+1):
        a = int(data[idx])
        idx +=1
        b = int(data[idx])
        idx +=1
        c = data[idx]
        idx +=1
        edges.append((a, b, c, edge_id))
        adj[a].append((b, c, edge_id))
        adj[b].append((a, c, edge_id))

    edges_from_1 = []
    for a, b, c, edge_id in edges:
        if a == 1 or b == 1:
            other = a if b == 1 else b
            edges_from_1.append((other, c, edge_id))

    edges_to_N = []
    for a, b, c, edge_id in edges:
        if a == N or b == N:
            other = a if b == N else b
            edges_to_N.append((other, c, edge_id))

    # Find a pair e in edges_from_1, f in edges_to_N with different labels
    found_e = None
    found_f = None
    # Check edges_from_1 first
    for e in edges_from_1:
        x_e, c_e, eid_e = e
        for f in edges_to_N:
            y_f, c_f, eid_f = f
            if c_e != c_f:
                found_e = e
                found_f = f
                break
        if found_e:
            break
    if not found_e:
        # Check edges_to_N first
        for f in edges_to_N:
            y_f, c_f, eid_f = f
            for e in edges_from_1:
                x_e, c_e, eid_e = e
                if c_e != c_f:
                    found_e = e
                    found_f = f
                    break
            if found_e:
                break

    if not found_e or not found_f:
        print(-1)
        return

    # Proceed with BFS
    x = found_e[0]
    y = found_f[0]
    eid_e = found_e[2]
    eid_f = found_f[2]

    # BFS from x to y to find the path, collecting edges
    prev_node = [-1] * (N + 1)
    prev_edge = [-1] * (N + 1)
    q = deque()
    q.append(x)
    prev_node[x] = x  # mark as visited
    while q:
        u = q.popleft()
        if u == y:
            break
        for (v, c, eid) in adj[u]:
            if prev_node[v] == -1:
                prev_node[v] = u
                prev_edge[v] = eid
                q.append(v)

    if prev_node[y] == -1:
        # no path found (impossible, as graph is connected)
        print(-1)
        return

    # Reconstruct path from x to y
    path_edges = []
    current = y
    while current != x:
        eid = prev_edge[current]
        if eid == -1:
            print(-1)
            return
        path_edges.append(eid)
        current = prev_node[current]
    path_edges.reverse()

    total_path = [eid_e] + path_edges + [eid_f]

    # Check length
    k = len(total_path)
    if k > 2 * N:
        print(-1)
        return

    print(k)
    for eid in total_path:
        print(eid)

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