結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:46:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,096 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 156,360 KB |
最終ジャッジ日時 | 2025-03-31 17:47:53 |
合計ジャッジ時間 | 7,518 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 11 WA * 3 |
ソースコード
import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 A = [] B_pool = [] C = [] for _ in range(N): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 c = int(input[ptr]) ptr += 1 A.append(a) B_pool.append(b) C.append(c) # Precompute for each group the valid B indices and their max contribution valid_Bs_for_groups = [] max_contributions = [] for i in range(N): a = A[i] c = C[i] valid = [] current_max = -1 for j in range(N): b_j = B_pool[j] if b_j == a or b_j == c: continue sum_abc = a + b_j + c x = min(a, b_j, c) z = max(a, b_j, c) y = sum_abc - x - z if y == a or y == c: valid.append(j) current = max(a, b_j, c) if current > current_max: current_max = current if not valid: print("NO") return valid_Bs_for_groups.append(valid) max_contributions.append(current_max) # Build the bipartite graph adjacency list graph = [[] for _ in range(N)] for i in range(N): graph[i] = valid_Bs_for_groups[i] # Hopcroft-Karp algorithm to find maximum matching def hopcroft_karp(): 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_null = float('inf') while queue: u = queue.popleft() if dist[u] < dist_null: for v in graph[u]: if pair_v[v] == -1: dist_null = dist[u] + 1 elif dist[pair_v[v]] == float('inf'): dist[pair_v[v]] = dist[u] + 1 queue.append(pair_v[v]) return dist_null != float('inf') def dfs(u): for v in graph[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 return result max_matching = hopcroft_karp() if max_matching != N: print("NO") return S_max = sum(max_contributions) if S_max >= M: print("YES") print("KADOMATSU!") else: print("YES") print("NO") if __name__ == "__main__": main()