結果

問題 No.1615 Double Down
ユーザー lam6er
提出日時 2025-04-09 21:01:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,583 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 89,512 KB
最終ジャッジ日時 2025-04-09 21:03:15
合計ジャッジ時間 8,442 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 WA * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import collections
from collections import defaultdict

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
    
    edges_by_z = defaultdict(list)
    for _ in range(L):
        X = int(input[ptr])-1; ptr +=1
        Y = int(input[ptr])-1; ptr +=1
        Z = int(input[ptr]); ptr +=1
        edges_by_z[Z].append( (X, Y) )
    
    sorted_zs = sorted(edges_by_z.keys(), reverse=True)
    used_X = set()
    used_Y = set()
    total = 0
    
    for z in sorted_zs:
        edges = []
        for X, Y in edges_by_z[z]:
            if X not in used_X and Y not in used_Y:
                edges.append( (X, Y) )
        if not edges:
            continue
        
        graph = defaultdict(list)
        for X, Y in edges:
            graph[X].append(Y)
        
        for X in graph:
            graph[X].sort(reverse=True)  # Reverse to process higher Y first
        
        match_to_Y = {}
        match_to_X = {}
        layers = {}
        
        def bfs():
            layers.clear()
            queue = collections.deque()
            for X in graph:
                if X not in match_to_X:
                    layers[X] = 0
                    queue.append(X)
            res = False
            while queue:
                X = queue.popleft()
                for Y in graph[X]:
                    if Y not in match_to_Y:
                        res = True
                    else:
                        if match_to_Y[Y] not in layers:
                            layers[match_to_Y[Y]] = layers[X] + 1
                            queue.append(match_to_Y[Y])
            return res
        
        def dfs(X):
            for Y in graph[X]:
                if Y not in match_to_Y or (match_to_Y[Y] in layers and layers[match_to_Y[Y]] == layers[X] + 1 and dfs(match_to_Y[Y])):
                    match_to_X[X] = Y
                    match_to_Y[Y] = X
                    return True
            layers[X] = -1
            return False
        
        result = 0
        while bfs():
            new_matches = 0
            for X in list(graph.keys()):
                if X not in match_to_X:
                    if dfs(X):
                        new_matches += 1
            result += new_matches
        
        for X in match_to_X:
            Y = match_to_X[X]
            used_X.add(X)
            used_Y.add(Y)
            total += (1 << z)
    
    print(total)

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