結果

問題 No.1640 簡単な色塗り
ユーザー lam6er
提出日時 2025-04-15 21:41:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,158 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 89,888 KB
最終ジャッジ日時 2025-04-15 21:43:46
合計ジャッジ時間 11,072 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    pairs = []
    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        pairs.append((a, b))
    
    last = [0] * (N + 1)  # 1-based
    present = [False] * (N + 1)
    for i in range(N):
        a, b = pairs[i]
        present[a] = True
        present[b] = True
        if i + 1 > last[a]:
            last[a] = i + 1
        if i + 1 > last[b]:
            last[b] = i + 1
    
    # Check if all balls are present
    for x in range(1, N + 1):
        if not present[x]:
            print("No")
            return
    
    used = [False] * (N + 1)
    ans = []
    for i in range(N):
        a, b = pairs[i]
        current_step = i + 1  # 1-based
        a_last = (last[a] == current_step)
        b_last = (last[b] == current_step)
        
        if a_last and b_last:
            if not used[a] and not used[b]:
                print("No")
                return
            if not used[a]:
                ans.append(a)
                used[a] = True
            else:
                ans.append(b)
                used[b] = True
        elif a_last:
            if not used[a]:
                ans.append(a)
                used[a] = True
            else:
                ans.append(b)
                if not used[b]:
                    used[b] = True
        elif b_last:
            if not used[b]:
                ans.append(b)
                used[b] = True
            else:
                ans.append(a)
                if not used[a]:
                    used[a] = True
        else:
            # Choose the one that is not used, if possible
            if not used[a]:
                ans.append(a)
                used[a] = True
            elif not used[b]:
                ans.append(b)
                used[b] = True
            else:
                ans.append(a)  # arbitrary choice
    
    # Final check
    for x in range(1, N + 1):
        if not used[x]:
            print("No")
            return
    
    print("Yes")
    for choice in ans:
        print(choice)

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