結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー lam6er
提出日時 2025-04-16 00:13:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,707 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 81,856 KB
実行使用メモリ 848,996 KB
最終ジャッジ日時 2025-04-16 00:14:56
合計ジャッジ時間 5,381 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 MLE * 1 -- * 171
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    X = int(input[idx]); Y = int(input[idx+1]); Z = int(input[idx+2]); idx +=3
    friends = [set() for _ in range(N+1)]  # 1-based
    for _ in range(M):
        a = int(input[idx]); b = int(input[idx+1]); idx +=2
        friends[a].add(b)
        friends[b].add(a)
    
    # Build non-friend adjacency list, sorted
    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)
        # Sort to ensure lex order
        non_friends[u].sort()
    
    # BFS: (current, visited_set, mask, path)
    # mask: 0b00 (none), 0b01 (Y), 0b10 (Z), 0b11 (both)
    start = X
    target_mask = 0b11
    visited_init = set([start])
    mask_init = 0
    if start == Y:
        mask_init |= 0b01
    if start == Z:
        mask_init |= 0b10
    queue = deque()
    queue.append( (start, visited_init, mask_init, [start]) )
    found = None
    
    visited_states = set()
    
    while queue:
        current, visited, mask, path = queue.popleft()
        
        # Check if we can return to X
        if current != X and len(path) >= 3:
            # Check if next node is X and forms a valid cycle
            if X in non_friends[current]:
                new_mask = mask
                if X == Y:
                    new_mask |= 0b01
                if X == Z:
                    new_mask |= 0b10
                if new_mask == target_mask:
                    # Check if all nodes except X are unique
                    participants = path + [X]
                    if len(set(participants)) == len(path):
                        found = participants
                        break
        
        # Generate next states
        for v in non_friends[current]:
            if v in visited:
                continue
            new_visited = set(visited)
            new_visited.add(v)
            new_mask = mask
            if v == Y:
                new_mask |= 0b01
            if v == Z:
                new_mask |= 0b10
            new_path = path + [v]
            # Check if this state has been visited before
            state = (v, frozenset(new_visited), new_mask)
            if state in visited_states:
                continue
            visited_states.add(state)
            queue.append( (v, new_visited, new_mask, new_path) )
    
    if found:
        k = len(found) -1
        print(k)
        print(' '.join(map(str, found)))
    else:
        print(-1)

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