結果

問題 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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0