結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,362 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 502,284 KB
最終ジャッジ日時 2025-03-26 15:58:48
合計ジャッジ時間 6,499 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 5 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    M = int(input[idx])
    idx +=1
    triplets = []
    B_list = []
    for _ in range(N):
        A = int(input[idx])
        idx +=1
        B = int(input[idx])
        idx +=1
        C = int(input[idx])
        idx +=1
        triplets.append( (A, B, C) )
        B_list.append(B)
    
    allowed_Bs = [[] for _ in range(N)]
    base = [0]*N
    for i in range(N):
        A, _, C = triplets[i]
        base_i = max(A, C)
        base[i] = base_i
        allowed = []
        for j in range(N):
            Bj = B_list[j]
            if Bj == A or Bj == C:
                continue
            sorted_vals = sorted([A, Bj, 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:
                allowed.append(j)
        if not allowed:
            print("NO")
            return
        allowed_Bs[i] = allowed
    
    graph = [[] for _ in range(N)]
    for i in range(N):
        for j in allowed_Bs[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 MinCostFlow:
        INF = 1 << 60
        
        def __init__(self, N):
            self.N = N
            self.graph = [[] for _ in range(N)]
        
        def add_edge(self, fr, to, cap, cost):
            forward = [to, cap, cost, None]
            backward = forward[3] = [fr, 0, -cost, forward]
            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
            while maxf >0:
                dist = [self.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[1] >0 and dist[e[0]] > dist[v] + e[2] + h[v] - h[e[0]]:
                            dist[e[0]] = dist[v] + e[2] + h[v] - h[e[0]]
                            prevv[e[0]] = v
                            preve[e[0]] = e
                            if not inqueue[e[0]]:
                                queue.append(e[0])
                                inqueue[e[0]] = True
                if dist[t] == self.INF:
                    return -1
                for v in range(N):
                    h[v] += dist[v] if dist[v] < self.INF else 0
                
                d = maxf
                v = t
                while v != s:
                    d = min(d, preve[v][1])
                    v = prevv[v]
                maxf -= d
                res += d * h[t]
                v = t
                while v != s:
                    e = preve[v]
                    e[1] -= d
                    e[3][1] += d
                    v = prevv[v]
            return res
    
    S = 0
    T = 2*N +1
    mcf = MinCostFlow(T+1)
    for i in range(N):
        mcf.add_edge(S, i+1, 1, 0)
    for j in range(N):
        mcf.add_edge(N+1 +j, T, 1, 0)
    for i in range(N):
        A, _, C = triplets[i]
        base_i = max(A, C)
        for j in allowed_Bs[i]:
            Bj = B_list[j]
            max_val = max(A, Bj, C)
            cost = -max_val
            mcf.add_edge(i+1, N+1 +j, 1, cost)
    total_cost = mcf.flow(S, T, N)
    if total_cost == -1:
        print("YES")
        print("NO")
        return
    sum_max = -total_cost
    if sum_max >= M:
        print("YES")
        print("KADOMATSU!")
    else:
        print("YES")
        print("NO")

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