結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー gew1fw
提出日時 2025-06-12 20:24:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,107 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 67,300 KB
最終ジャッジ日時 2025-06-12 20:24:35
合計ジャッジ時間 12,913 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 171
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import itertools

def main():
    N, M = map(int, sys.stdin.readline().split())
    X, Y, Z = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(M):
        a, b = map(int, sys.stdin.readline().split())
        if a > b:
            a, b = b, a
        edges.add((a, b))
    
    # Construct complement graph
    complement = [[False] * (N + 1) for _ in range(N + 1)]
    for u in range(1, N + 1):
        for v in range(u + 1, N + 1):
            if (u, v) not in edges and (v, u) not in edges:
                complement[u][v] = True
                complement[v][u] = True
    
    # For each possible subset size starting from 3
    for k in range(3, N + 1):
        # We need at least 3 nodes: X, Y, Z
        if k < 3:
            continue
        # Generate all possible subsets of size k that include X, Y, Z
        others = [node for node in range(1, N + 1) if node not in {X, Y, Z}]
        # We need to select (k-3) nodes from others
        if k - 3 > len(others):
            continue
        for selected in itertools.combinations(others, k - 3):
            S = {X, Y, Z} | set(selected)
            # Generate all possible permutations of S starting with X and ending with X
            remaining = list(S - {X})
            # Generate all possible permutations of remaining
            for perm in itertools.permutations(remaining):
                # Form the permutation
                P = [X] + list(perm) + [X]
                # Check if all consecutive pairs are connected in complement graph
                valid = True
                for i in range(len(P) - 1):
                    u = P[i]
                    v = P[i+1]
                    if u == v:
                        valid = False
                        break
                    if not complement[u][v]:
                        valid = False
                        break
                if valid:
                    print(k)
                    print(' '.join(map(str, P)))
                    return
    # If no solution found
    print(-1)

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