結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:44:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 5,452 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 541,660 KB
最終ジャッジ日時 2025-04-15 23:47:17
合計ジャッジ時間 5,653 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 5 MLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

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)
    
    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()
0