結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー titia
提出日時 2026-01-06 03:28:39
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 2,309 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 565 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 78,348 KB
最終ジャッジ日時 2026-01-06 03:28:43
合計ジャッジ時間 3,561 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N=int(input())

U=[input().strip() for i in range(N)]

#X="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
#D={X[i]:i for i in range(len(X))}

#V=[]
#for u in U:
#    a=[D[u[i]] for i in range(3)]
#    V.append(a)

LEN=N*2

if N>52:
    print("Impossible")
    exit()

EDGE=[[] for i in range(LEN)]
EDGE_INV=[[] for i in range(LEN)]

# 0～N : X_i
# N+1～2N: Y_i = ￢X_i

for i in range(N):
    a=U[i][:2]
    b=U[i][2]
    
    c=U[i][0]
    d=U[i][1:]
    
    for j in range(i+1,N):
        e=U[j][:2]
        f=U[j][2]
        
        g=U[j][0]
        h=U[j][1:]

        if a==e or b==f:
            EDGE[i].append(N+j)
            EDGE[j].append(N+i)

            EDGE_INV[N+j].append(i)
            EDGE_INV[N+i].append(j)

        if a==h or b==g:
            EDGE[i].append(j)
            EDGE[N+j].append(N+i)

            EDGE_INV[j].append(i)
            EDGE_INV[N+i].append(N+j)

        if c==f or d==e:
            EDGE[N+i].append(N+j)
            EDGE[j].append(i)

            EDGE_INV[N+j].append(N+i)
            EDGE_INV[i].append(j)

        if c==g or d==h:
            EDGE[N+i].append(j)
            EDGE[N+j].append(i)

            EDGE_INV[j].append(N+i)
            EDGE_INV[i].append(N+j)

QUE = list(range(2*N))
check=[0]*(2*N)
TOP_SORT=[]

def dfs(x):
    if check[x]==1:
        return
    check[x]=1
    
    for to in EDGE[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x) # 全ての点からDFSを行い, 帰りがけに点を答えに入れる
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

USE=[0]*(2*N)
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in EDGE_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in TOP_SORT[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))


PLACE=[-1]*(2*N)
for i in range(len(SCC)):
    for x in SCC[i]:
        PLACE[x]=i

ANS=[-1]*N
flag=1
for i in range(N):
    if PLACE[i]==PLACE[N+i]:
        flag=0
        break
    
    elif PLACE[i]>PLACE[N+i]:
        ANS[i]=U[i][:2],U[i][2]
    else:
        ANS[i]=U[i][0],U[i][1:]
    
if flag==0:
    print("Impossible")
else:
    for ans in ANS:
        print(*ans)
0