結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー lam6er
提出日時 2025-03-26 15:57:33
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,378 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 849,112 KB
最終ジャッジ日時 2025-03-26 15:58:31
合計ジャッジ時間 10,377 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 171
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    x = int(data[idx])
    idx += 1
    y = int(data[idx])
    idx += 1
    z = int(data[idx])
    idx += 1

    friends = [set() for _ in range(n + 1)]
    for _ in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        friends[a].add(b)
        friends[b].add(a)

    complement = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j and j not in friends[i]:
                complement[i].append(j)
        complement[i].sort()

    visited = set()
    queue = deque()
    initial_visited_mask = 0
    queue.append((x, 0, initial_visited_mask, [x]))

    found = False
    answer = []

    while queue:
        current_node, mask, visited_mask, path = queue.popleft()

        if current_node == x and len(path) > 1:
            if mask == 0b11:
                if path[-2] not in friends[x]:
                    answer = path
                    found = True
                    break

        next_nodes = complement[current_node]
        for next_node in next_nodes:
            if next_node == x:
                if mask == 0b11 and len(path) >= 3:
                    new_path = path + [x]
                    state = (x, mask, visited_mask)
                    if state not in visited:
                        visited.add(state)
                        queue.append((x, mask, visited_mask, new_path))
                continue

            if (visited_mask & (1 << (next_node - 1))) != 0:
                continue

            new_mask = mask
            if next_node == y:
                new_mask |= 0b01
            if next_node == z:
                new_mask |= 0b10

            new_visited_mask = visited_mask | (1 << (next_node - 1))
            new_path = path + [next_node]

            state = (next_node, new_mask, new_visited_mask)
            if state not in visited:
                visited.add(state)
                queue.append((next_node, new_mask, new_visited_mask, new_path))

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

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