結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:50:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,853 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 157,764 KB
最終ジャッジ日時 2025-06-12 20:55:01
合計ジャッジ時間 13,525 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 9 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    groups = []
    B_list = []
    for _ in range(N):
        A, B, C = map(int, sys.stdin.readline().split())
        groups.append((A, B, C))
        B_list.append(B)
    
    possible = True
    adj = [[] for _ in range(N)]
    for i in range(N):
        A, B, C = groups[i]
        X = max(A, C)
        valid_Bs = []
        for j in range(N):
            B_j = B_list[j]
            a, b, c = A, B_j, C
            if a == b or b == c or a == c:
                continue
            sorted_vals = sorted([a, b, c])
            mid = sorted_vals[1]
            if mid == a or mid == c:
                valid_Bs.append(j)
        if not valid_Bs:
            possible = False
            break
        adj[i] = valid_Bs
    
    if not possible:
        print("NO")
        return
    
    pair_U = [-1] * N
    pair_V = [-1] * N
    dist = [0] * N

    def bfs():
        queue = deque()
        for u in range(N):
            if pair_U[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist_found = float('inf')
        while queue:
            u = queue.popleft()
            if dist[u] < dist_found:
                for v in adj[u]:
                    if pair_V[v] == -1:
                        dist_found = dist[u] + 1
                    elif dist[pair_V[v]] == float('inf'):
                        dist[pair_V[v]] = dist[u] + 1
                        queue.append(pair_V[v])
        return dist_found != float('inf')

    def dfs(u):
        for v in adj[u]:
            if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u] + 1 and dfs(pair_V[v])):
                pair_U[u] = v
                pair_V[v] = u
                return True
        dist[u] = float('inf')
        return False

    result = 0
    while bfs():
        for u in range(N):
            if pair_U[u] == -1:
                if dfs(u):
                    result += 1
    if result < N:
        print("NO")
        return

    max_weight = 0
    for i in range(N):
        A, B, C = groups[i]
        max_val = max(A, C)
        for j in adj[i]:
            B_j = B_list[j]
            a, b, c = A, B_j, C
            if a == b or b == c or a == c:
                continue
            sorted_vals = sorted([a, b, c])
            mid = sorted_vals[1]
            if mid != a and mid != c:
                continue
            current_max = max(a, b, c)
            if current_max > max_val:
                max_val = current_max
                break
        max_weight += max_val

    if max_weight >= M:
        print("YES")
        print("KADOMATSU!")
    else:
        print("YES")
        print("NO")

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