結果

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

ソースコード

diff # 

import sys
import heapq
from collections import defaultdict
from bisect import bisect_left, bisect_right

class Edge:
    def __init__(self, to, rev, cap, cost):
        self.to = to
        self.rev = rev
        self.cap = cap
        self.cost = cost

class MinCostFlow:
    def __init__(self, N):
        self.N = N
        self.graph = [[] for _ in range(N)]
    
    def add_edge(self, fr, to, cap, cost):
        forward = Edge(to, len(self.graph[to]), cap, 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  # potential
        prevv = [0] * N
        preve = [0] * N
        INF = float('inf')
        while maxf > 0:
            dist = [INF] * N
            dist[s] = 0
            heap = []
            heapq.heappush(heap, (0, s))
            while heap:
                d, v = heapq.heappop(heap)
                if dist[v] < d:
                    continue
                for i, e in enumerate(self.graph[v]):
                    if e.cap > 0 and dist[e.to] > d + e.cost + h[v] - h[e.to]:
                        dist[e.to] = d + e.cost + h[v] - h[e.to]
                        prevv[e.to] = v
                        preve[e.to] = i
                        heapq.heappush(heap, (dist[e.to], e.to))
            if dist[t] == INF:
                return -1  # no more flow
            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]].cap)
                v = prevv[v]
            maxf -= d
            res += d * h[t]
            v = t
            while v != s:
                e = self.graph[prevv[v]][preve[v]]
                e.cap -= d
                self.graph[v][e.rev].cap += d
                v = prevv[v]
        return res

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    groups = []
    all_B = []
    for _ in range(N):
        A = int(input[ptr])
        ptr += 1
        B = int(input[ptr])
        ptr += 1
        C = int(input[ptr])
        ptr += 1
        groups.append((A, B, C))
        all_B.append(B)
    
    B_count = defaultdict(int)
    for b in all_B:
        B_count[b] += 1
    sorted_B = sorted(B_count.keys())
    K = len(sorted_B)
    B_to_idx = {b: i for i, b in enumerate(sorted_B)}
    
    S = []
    possible = True
    for i in range(N):
        A_i, _, C_i = groups[i]
        candidates = []
        if A_i < C_i:
            left = bisect_left(sorted_B, A_i)
            for b in sorted_B[:left]:
                if b != A_i and b != C_i:
                    candidates.append(b)
            right = bisect_right(sorted_B, C_i)
            for b in sorted_B[right:]:
                if b != A_i and b != C_i:
                    candidates.append(b)
        else:
            left = bisect_left(sorted_B, C_i)
            for b in sorted_B[:left]:
                if b != A_i and b != C_i:
                    candidates.append(b)
            right = bisect_right(sorted_B, A_i)
            for b in sorted_B[right:]:
                if b != A_i and b != C_i:
                    candidates.append(b)
        valid_b = []
        for b in candidates:
            vals = sorted([A_i, b, C_i])
            if vals[1] == A_i or vals[1] == C_i:
                valid_b.append(b)
        if not valid_b:
            possible = False
        S.append(valid_b)
    
    if not possible:
        print("NO")
        return
    
    total_nodes = 1 + N + K + 1
    mcf = MinCostFlow(total_nodes)
    S_node = 0
    T_node = 1 + N + K
    
    for i in range(N):
        mcf.add_edge(S_node, 1 + i, 1, 0)
    
    for i in range(N):
        A_i, _, C_i = groups[i]
        for b in S[i]:
            p = max(A_i, b, C_i)
            b_idx = 1 + N + B_to_idx[b]
            mcf.add_edge(1 + i, b_idx, 1, -p)
    
    for idx, b in enumerate(sorted_B):
        b_idx = 1 + N + idx
        cap = B_count[b]
        mcf.add_edge(b_idx, T_node, cap, 0)
    
    total_cost = mcf.flow(S_node, T_node, N)
    if total_cost == -1:
        print("NO")
        return
    
    sum_p = -total_cost
    if sum_p >= M:
        print("YES")
        print("KADOMATSU!")
    else:
        print("YES")
        print("NO")

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