結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー gew1fw
提出日時 2025-06-12 13:00:25
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,170 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 849,132 KB
最終ジャッジ日時 2025-06-12 13:06:47
合計ジャッジ時間 9,463 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 171
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    X = int(input[ptr])
    ptr += 1
    Y = int(input[ptr])
    ptr += 1
    Z = int(input[ptr])
    ptr += 1

    friends = [set() for _ in range(N + 1)]
    for _ in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        friends[a].add(b)
        friends[b].add(a)

    # Build non-friend adjacency list, sorted lex
    non_friends = [[] for _ in range(N + 1)]
    for u in range(1, N + 1):
        for v in range(1, N + 1):
            if u != v and v not in friends[u]:
                non_friends[u].append(v)
        non_friends[u].sort()

    # Nodes excluding X
    nodes_excluding_x = sorted([u for u in range(1, N + 1) if u != X])
    if not nodes_excluding_x:
        print(-1)
        return
    bit_position = {u: idx for idx, u in enumerate(nodes_excluding_x)}

    # BFS initialization
    queue = deque()
    initial_path = [X]
    queue.append((X, 0, False, False, initial_path))
    visited = dict()
    initial_key = (X, 0, False, False)
    visited[initial_key] = 0  # path length is 0 (only X)

    found = False
    answer = None

    while queue:
        current_node, mask, has_y, has_z, path = queue.popleft()
        current_path_len = len(path) - 1

        # Check if current node is X and path is valid
        if current_node == X and len(path) > 1:
            if has_y and has_z:
                prev_node = path[-2]
                if prev_node not in friends[X]:
                    answer = path
                    found = True
                    break

        # Explore neighbors
        for neighbor in non_friends[current_node]:
            if neighbor == X:
                # Check if can return to X
                if current_node in friends[X]:
                    continue
                if has_y and has_z:
                    new_path = path + [X]
                    answer = new_path
                    found = True
                    break
                continue

            # Check if neighbor is not X and not visited
            if neighbor not in bit_position:
                continue  # should not happen
            bit = bit_position[neighbor]
            if (mask & (1 << bit)) != 0:
                continue  # already visited

            new_mask = mask | (1 << bit)
            new_has_y = has_y or (neighbor == Y)
            new_has_z = has_z or (neighbor == Z)
            new_path = path + [neighbor]
            new_path_len = len(new_path) - 1

            state_key = (neighbor, new_mask, new_has_y, new_has_z)
            if state_key in visited:
                if visited[state_key] <= new_path_len:
                    continue
            visited[state_key] = new_path_len
            queue.append((neighbor, new_mask, new_has_y, new_has_z, new_path))

        if found:
            break

    if found:
        k = len(answer) - 1
        print(k)
        print(' '.join(map(str, answer)))
    else:
        print(-1)

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