結果

問題 No.1776 Love Triangle 2 (Hard)
ユーザー lam6er
提出日時 2025-04-16 00:10:14
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,021 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 848,036 KB
最終ジャッジ日時 2025-04-16 00:11:14
合計ジャッジ時間 4,315 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)]
    for _ in range(M):
        a = int(input[idx]); b = int(input[idx+1]); idx +=2
        friends[a].add(b)
        friends[b].add(a)
    
    # Build complement graph
    complement = [[] 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]:
                complement[u].append(v)
    
    # BFS
    # state: (current_node, visited_nodes (set), mask, path)
    # mask: 0b00 (no Y/Z), 0b01 (Y), 0b10 (Z), 0b11 (both)
    min_length = None
    best_path = None
    initial_visited = set()
    queue = deque()
    queue.append( (X, initial_visited, 0, [X]) )
    
    while queue:
        current, visited, mask, path = queue.popleft()
        
        if current == X and mask == 0b11 and len(path) >=4:
            # Check if valid
            valid = True
            for i in range(len(path)-1):
                u = path[i]
                v = path[i+1]
                if v in friends[u]:
                    valid = False
                    break
            # Check all nodes except X are unique
            seen = set()
            for node in path[1:-1]:
                if node in seen:
                    valid = False
                    break
                seen.add(node)
            if valid:
                k = len(path) -1
                if (min_length is None) or (k < min_length) or (k == min_length and path < best_path):
                    min_length = k
                    best_path = path.copy()
            continue
        
        for neighbor in complement[current]:
            if neighbor == X:
                if len(path) >=3 and (neighbor not in path[1:-1]):
                    new_mask = mask
                    new_path = path + [neighbor]
                    new_visited = visited.copy()
                    # Check if Y and Z are in new_path
                    has_Y = (Y in new_path)
                    has_Z = (Z in new_path)
                    if has_Y and has_Z:
                        # Add to queue to check validity
                        queue.append( (neighbor, new_visited, new_mask, new_path) )
                continue
            if neighbor in visited:
                continue
            new_visited = visited.copy()
            new_visited.add(neighbor)
            new_mask = mask
            if neighbor == Y:
                new_mask |= 0b01
            if neighbor == Z:
                new_mask |= 0b10
            new_path = path + [neighbor]
            queue.append( (neighbor, new_visited, new_mask, new_path) )
    
    if min_length is None:
        print(-1)
    else:
        print(min_length)
        print(' '.join(map(str, best_path)))

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