結果

問題 No.1615 Double Down
ユーザー qwewe
提出日時 2025-04-24 12:21:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,122 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 96,472 KB
最終ジャッジ日時 2025-04-24 12:23:44
合計ジャッジ時間 11,627 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict, deque

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

    max_z = dict()

    for _ in range(L):
        X = int(input[ptr]); ptr +=1
        Y = int(input[ptr]); ptr +=1
        Z = int(input[ptr]); ptr +=1
        if (X, Y) not in max_z or Z > max_z[(X, Y)]:
            max_z[(X, Y)] = Z

    # Group edges by Z
    z_groups = defaultdict(list)
    for (X, Y), z in max_z.items():
        z_groups[z].append((X, Y))

    # Sort Z groups in descending order
    sorted_zs = sorted(z_groups.keys(), reverse=True)

    matched_buyers = [False] * (N + 1)  # 1-based
    matched_items = [False] * (M + 1)    # 1-based
    total = 0

    for z in sorted_zs:
        edges = []
        for X, Y in z_groups[z]:
            if not matched_buyers[X] and not matched_items[Y]:
                edges.append((X, Y))
        if not edges:
            continue

        # Sort edges in descending order of Y, then X
        edges.sort(key=lambda x: (-x[1], -x[0]))

        # Build adjacency list for buyers
        adj = defaultdict(list)
        y_to_edges = defaultdict(list)
        for X, Y in edges:
            adj[X].append(Y)
            y_to_edges[Y].append(X)

        # Hopcroft-Karp algorithm
        pair_U = {u: None for u in (X for X, Y in edges)}
        pair_V = {v: None for v in (Y for X, Y in edges)}
        dist = {}

        def bfs():
            queue = deque()
            for u in pair_U:
                if pair_U[u] is None:
                    dist[u] = 0
                    queue.append(u)
                else:
                    dist[u] = float('inf')
            dist[None] = float('inf')
            while queue:
                u = queue.popleft()
                if u is not None:
                    for v in adj[u]:
                        if dist.get(pair_V[v], float('inf')) == float('inf'):
                            dist[pair_V[v]] = dist[u] + 1
                            queue.append(pair_V[v])
            return dist[None] != float('inf')

        def dfs(u):
            if u is not None:
                for v in adj[u]:
                    if dist.get(pair_V[v], float('inf')) == dist[u] + 1:
                        if dfs(pair_V[v]):
                            pair_U[u] = v
                            pair_V[v] = u
                            return True
                dist[u] = float('inf')
                return False
            return True

        result = 0
        while bfs():
            for u in pair_U:
                if pair_U[u] is None:
                    if dfs(u):
                        result += 1
        # Now, pair_U has the matching
        for u, v in pair_U.items():
            if v is not None:
                if not matched_buyers[u] and not matched_items[v]:
                    total += (1 << z)
                    matched_buyers[u] = True
                    matched_items[v] = True

    print(total)

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