結果

問題 No.1612 I hate Construct a Palindrome
ユーザー 👑 SPD_9X2
提出日時 2021-07-21 22:52:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 3,866 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 142,352 KB
最終ジャッジ日時 2024-07-17 19:56:29
合計ジャッジ時間 8,177 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
全部が同じ種類の辺なら不可能
そうでないなら、2種類の文字を使うパスを見付ける
あとは、半分を同じ文字で埋める
start が 2色
goal が2色
ならそのうち使われなかった方を繰り返しに採用する
それ以外なら、適当に辺を持ってくる
"""
from sys import stdin
import sys
from collections import deque
N,M = map(int,stdin.readline().split())
#olis = [ [] for i in range(N) ]
lis = [ [] for i in range(N) ]
C = []
AB = []
for i in range(M):
    A,B,tC = stdin.readline().split()
    A = int(A)
    B = int(B)
    tC = ord(tC)
    A -= 1
    B -= 1
    C.append( tC )
    AB.append((A,B))
    lis[A].append( (B,i) )
    lis[B].append( (A,i) )
#2色のパスを見付ける必要がある
Cset = set(C)
if len(Cset) == 1:
    print (-1)
    sys.exit()
sc = set()
gc = set()
for nex,ind in lis[0]:
    sc.add(C[ind])
for nex,ind in lis[N-1]:
    gc.add(C[ind])
sc = list(sc)
gc = list(gc)
if len(sc) > 1 or len(gc) > 1:
    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N
    q = deque([0])
    dlis[0] = 0
    while q:
        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)
    ans = []
    nv = N-1
    while nv != 0:
        ans.append( elis[nv] )
        nv = plis[nv]
    if len(sc) > 1:
        fe = None
        for nex,ind in lis[0]:
            if C[ind] != C[ans[-1]]:
                fe = ind
                break
        while len(ans) + 2 <= 2*N:
            ans.append(fe)
            ans.append(fe)
        ans.reverse()
        for i in range(len(ans)):
            ans[i] += 1
        print (len(ans))
        print ("\n".join(map(str,ans)))
        sys.exit()
    else:
        ge = None
        ans.reverse()
        
        for nex,ind in lis[0]:
            if C[ind] != C[ans[-1]]:
                ge = ind
                break
        while len(ans) + 2 <= 2*N:
            ans.append(ge)
            ans.append(ge)
        for i in range(len(ans)):
            ans[i] += 1
        print (len(ans))
        print ("\n".join(map(str,ans)))
        sys.exit()
else:
    lastc = gc[0]
    wante = None
    for i in range(M):
        if C[i] != lastc:
            wante = i
            break
    wA,wB = AB[wante]
    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N
    q = deque([0])
    dlis[0] = 0
    while q:
        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)
    zlast = wA if dlis[wA] < dlis[wB] else wB
    zans = []
    nv = zlast
    while nv != 0:
        zans.append(elis[nv])
        nv = plis[nv]
    zans.reverse()
    
    dlis = [float("inf")] * N
    plis = [i for i in range(N)]
    elis = [None] * N
    q = deque([N-1])
    dlis[N-1] = 0
    while q:
        v = q.popleft()
        for nex,ind in lis[v]:
            if dlis[nex] > dlis[v] + 1:
                dlis[nex] = dlis[v] + 1
                plis[nex] = v
                elis[nex] = ind
                q.append(nex)
    nlast = wA if dlis[wA] < dlis[wB] else wB
    nans = []
    nv = nlast
    while nv != N-1:
        nans.append(elis[nv])
        nv = plis[nv]
    if zlast == nlast:
        zans.append(wante)
        zans.append(wante)
    else:
        zans.append(wante)
    ans = zans + nans
    while len(ans) + 2 <= 2*N:
        ans.append(lis[N-1][0][1])
        ans.append(ans[-1])
    for i in range(len(ans)):
        ans[i] += 1
    print (len(ans))
    print ("\n".join(map(str,ans)))
    sys.exit()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0