結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:53:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,853 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 158,132 KB |
最終ジャッジ日時 | 2025-06-12 15:54:04 |
合計ジャッジ時間 | 11,852 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 9 WA * 5 |
ソースコード
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()