結果

問題 No.2403 "Eight" Bridges of Königsberg
ユーザー qwewe
提出日時 2025-05-14 12:49:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,561 bytes
コンパイル時間 229 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 123,392 KB
最終ジャッジ日時 2025-05-14 12:51:15
合計ジャッジ時間 5,090 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

sys.setrecursionlimit(1 << 25)

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
    
    edges = []
    in_degree = defaultdict(int)
    out_degree = defaultdict(int)
    
    for _ in range(M):
        u = int(data[idx])-1
        idx +=1
        v = int(data[idx])-1
        idx +=1
        edges.append( (u, v) )
        out_degree[u] +=1
        in_degree[v] +=1
    
    delta = [0]*N
    for i in range(N):
        delta[i] = out_degree.get(i,0) - in_degree.get(i,0)
    
    # Compute S for option 1
    S = sum( max(-d, 0) for d in delta )
    
    # Compute sum_AB for option 2
    has_s_ge1 = any( d >=1 for d in delta )
    has_t_lt_1 = any( d < -1 for d in delta )
    
    def compute_A(s_d):
        if s_d >=1:
            return 0
        elif 0 <= s_d <1:
            return 1 - s_d
        else: # s_d <0
            return 1
    
    def compute_B(t_d):
        if t_d >=0:
            return 0
        elif -1 <= t_d <0:
            return t_d
        else: # t_d < -1
            return -1
    
    if has_s_ge1 and has_t_lt_1:
        sum_AB = -1
    else:
        # compute min_A
        if has_s_ge1:
            min_A = 0
        else:
            min_A = float('inf')
            for d in delta:
                a = compute_A(d)
                if a < min_A:
                    min_A = a
        # compute min_B
        if has_t_lt_1:
            min_B = -1
        else:
            min_B = float('inf')
            for d in delta:
                b = compute_B(d)
                if b < min_B:
                    min_B = b
        sum_AB = min_A + min_B
    
    K_delta = min(S, S + sum_AB)
    
    # Compute connected components using Union-Find
    parent = list(range(N))
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root != v_root:
            parent[v_root] = u_root
    for u, v in edges:
        union(u, v)
    # Now, count the number of connected components
    roots = set()
    for i in range(N):
        roots.add(find(i))
    C = len(roots)
    
    if C ==1:
        print(K_delta)
    else:
        required = C-1
        if K_delta >= required:
            print(K_delta)
        else:
            print(-1)
    
if __name__ == '__main__':
    main()
0