結果

問題 No.470 Inverse S+T Problem
コンテスト
ユーザー mkawa2
提出日時 2020-05-01 12:01:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 3,127 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 16,512 KB
最終ジャッジ日時 2024-12-22 13:58:47
合計ジャッジ時間 2,365 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#import matplotlib.pyplot as plt
#import networkx as nx
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

# 2-SATらしい
def main():
    n=II()
    ss=[SI() for _ in range(n)]

    # 1文字の文字列が大小アルファベットの26*2=52種類しかないので、それより多いと無理
    if n>52:
        print("Impossible")
        exit()

    # 「i番目の文字列を左で切ること」を頂点iとする
    # 「i番目の文字列を右で切ること」を頂点n+iとする
    # 分割してできる文字列ごとに頂点をまとめる
    cnt=defaultdict(list)
    for i,s in enumerate(ss):
        cnt[s[0]].append(i)
        cnt[s[1:]].append(i)
        cnt[s[2]].append(i+n)
        cnt[s[:2]].append(i+n)
    #print(cnt)

    # 同じ文字列ができる頂点のうち、使えるのは１つだけ
    # 例えば"ab":[2,3,5]であれば、頂点2が"ab"を使えば頂点3,5は使えない
    # つまり、頂点2を使う場合は、頂点3,5の逆の切り方（+nか-nしたもの）を選ばなくてはいけない
    # よって、2→3,5の逆、3→2,5の逆、5→2,3の逆に辺を張ればよい
    # 強連結成分分解(SCC)のために逆辺(ot)も持っておく
    #G=nx.DiGraph()
    #G.add_edges_from(range(2*n))
    to=[[] for _ in range(n*2)]
    ot=[[] for _ in range(n*2)]
    for uu in cnt.values():
        for u in uu:
            for v in uu:
                if u==v:continue
                v=(v+n)%(2*n)
                if u==v:continue
                to[u].append(v)
                ot[v].append(u)
                #G.add_edge(u,v)
    #print(to)

    # こっからSCC
    # トポロジカル順を作る
    def dfs(u):
        for v in to[u]:
            if fin[v]:continue
            fin[v]=True
            dfs(v)
        top.append(u)

    top=[]
    fin=[False]*(2*n)
    for u in range(2*n):
        if fin[u]:continue
        fin[u]=True
        dfs(u)
    top.reverse()
    #print(top)

    # 逆辺を辿って強結合を探す
    def rdfs(u,k):
        for v in ot[u]:
            if com[v]!=-1:continue
            com[v]=k
            rdfs(v,k)

    com=[-1]*(2*n)
    k=0
    for u in top:
        if com[u]!=-1:continue
        com[u]=k
        rdfs(u,k)
        k+=1
    #print(com)

    # 同じ文字列の異なる切り方(頂点uとu+n)が強連結になっていたら、解なし
    for u in range(n):
        if com[u]==com[u+n]:
            print("Impossible")
            exit()

    # 各文字列について、トポロジカル順が後(強連結成分の番号が大きい)の切り方を選ぶ
    for u,s in enumerate(ss):
        if com[u]>com[u+n]:print(s[0],s[1:])
        else:print(s[:2],s[2])

    #nx.draw_networkx(G)
    #plt.show()

main()
0