結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:26:58 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 5,452 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 592,208 KB |
最終ジャッジ日時 | 2025-04-16 16:28:23 |
合計ジャッジ時間 | 6,371 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 5 MLE * 1 -- * 8 |
ソースコード
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) valid_for_group = [[] for _ in range(N)] for i in range(N): A, _, C = groups[i] for j in range(N): B_j = B_list[j] if A == B_j or B_j == C or A == C: continue sorted_vals = sorted([A, B_j, C]) if sorted_vals[0] == sorted_vals[1] or sorted_vals[1] == sorted_vals[2]: continue if sorted_vals[1] == A or sorted_vals[1] == C: valid_for_group[i].append(j) if not valid_for_group[i]: print("NO") return graph = [[] for _ in range(N)] for i in range(N): for j in valid_for_group[i]: graph[i].append(j) 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 == N if not hopcroft_karp(): print("NO") return from heapq import heappush, heappop class Edge: def __init__(self, to, rev, capacity, cost): self.to = to self.rev = rev self.capacity = capacity self.cost = cost class MinCostFlow: def __init__(self, N): self.N = N self.graph = [[] for _ in range(N)] def add_edge(self, fr, to, capacity, cost): forward = Edge(to, len(self.graph[to]), capacity, cost) backward = Edge(fr, len(self.graph[fr]), 0, -cost) self.graph[fr].append(forward) self.graph[to].append(backward) def flow(self, s, t, maxf): N = self.N res = 0 h = [0] * N prevv = [0] * N preve = [0] * N INF = float('inf') while maxf > 0: dist = [INF] * N dist[s] = 0 inqueue = [False] * N queue = deque() queue.append(s) inqueue[s] = True while queue: v = queue.popleft() inqueue[v] = False for i, e in enumerate(self.graph[v]): if e.capacity > 0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]: dist[e.to] = dist[v] + e.cost + h[v] - h[e.to] prevv[e.to] = v preve[e.to] = i if not inqueue[e.to]: queue.append(e.to) inqueue[e.to] = True if dist[t] == INF: return -1 for v in range(N): h[v] += dist[v] if dist[v] < INF else 0 d = maxf v = t while v != s: d = min(d, self.graph[prevv[v]][preve[v]].capacity) v = prevv[v] maxf -= d res += d * h[t] v = t while v != s: e = self.graph[prevv[v]][preve[v]] e.capacity -= d self.graph[v][e.rev].capacity += d v = prevv[v] return res source = 0 sink = 2 * N + 1 mcf = MinCostFlow(sink + 1) for i in range(N): mcf.add_edge(source, i + 1, 1, 0) for j in range(N): mcf.add_edge(N + 1 + j, sink, 1, 0) for i in range(N): A, _, C = groups[i] for j in valid_for_group[i]: B_j = B_list[j] max_val = max(A, B_j, C) cost = -max_val mcf.add_edge(i + 1, N + 1 + j, 1, cost) total_cost = mcf.flow(source, sink, N) if total_cost == -1: print("NO") return total_sum = -total_cost print("YES") if total_sum >= M: print("KADOMATSU!") else: print("NO") if __name__ == '__main__': main()