結果

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

ソースコード

diff # 

from collections import defaultdict, deque

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):
        INF = float('inf')
        res = 0
        h = [0] * self.N  # Potential
        prevv = [0] * self.N
        preve = [0] * self.N
        flow = 0
        while maxf > 0:
            dist = [INF] * self.N
            inqueue = [False] * self.N
            dist[s] = 0
            q = deque()
            q.append(s)
            inqueue[s] = True
            while q:
                v = q.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]:
                            q.append(e.to)
                            inqueue[e.to] = True
            if dist[t] == INF:
                break
            for v in range(self.N):
                if dist[v] < INF:
                    h[v] += dist[v]
            d = maxf
            v = t
            while v != s:
                d = min(d, self.graph[prevv[v]][preve[v]].capacity)
                v = prevv[v]
            flow += d
            res += d * h[t]
            maxf -= d
            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 flow, res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    groups = []
    B_list = []
    for _ in range(N):
        A = int(data[idx])
        B = int(data[idx+1])
        C = int(data[idx+2])
        groups.append((A, B, C))
        B_list.append(B)
        idx +=3
    
    # Count B occurrences
    cnt = defaultdict(int)
    for b in B_list:
        cnt[b] += 1
    unique_B = list(cnt.keys())
    K = len(unique_B)
    B_index = {v: i + N + 1 for i, v in enumerate(unique_B)}
    
    # Preprocess candidates for each group
    candidates = []
    for i in range(N):
        A, _, C = groups[i]
        valid = []
        for v in unique_B:
            if A == v or v == C or A == C:
                continue
            max_val = max(A, v, C)
            min_val = min(A, v, C)
            mid_val = A + v + C - max_val - min_val
            if mid_val == A or mid_val == C:
                valid.append((v, max_val))
        # Sort by max_val descending
        valid.sort(key=lambda x: -x[1])
        candidates.append(valid)
    
    # Check if any group has no candidates
    for i in range(N):
        if not candidates[i]:
            print("NO")
            return
    
    # Build the flow network
    S = 0
    T = N + K + 1
    mcf = MinCostFlow(N + K + 2)
    
    # Source to groups
    for i in range(1, N+1):
        mcf.add_edge(S, i, 1, 0)
    
    # Groups to B nodes
    for i in range(N):
        group_id = i + 1
        for v, max_val in candidates[i]:
            b_node = B_index[v]
            mcf.add_edge(group_id, b_node, 1, -max_val)  # Negative for min cost
    
    # B nodes to sink
    for v in unique_B:
        b_node = B_index[v]
        cap = cnt[v]
        mcf.add_edge(b_node, T, cap, 0)
    
    # Compute flow
    flow, cost = mcf.flow(S, T, N)
    if flow != N:
        print("NO")
    else:
        total = -cost
        if total >= M:
            print("YES")
            print("KADOMATSU!")
        else:
            print("YES")
            print("NO")

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