結果

問題 No.3079 Unite Japanese Prefectures
コンテスト
ユーザー 👑 binap
提出日時 2025-02-19 02:16:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,664 ms / 4,000 ms
コード長 1,806 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 271,768 KB
最終ジャッジ日時 2025-03-16 10:22:56
合計ジャッジ時間 22,297 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

# convert the following submission
# https://yukicoder.me/submissions/1044008

import sys
from functools import lru_cache
from collections import defaultdict

sys.setrecursionlimit(10**6)
input = sys.stdin.read

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, rank, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        if rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        elif rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

def main():
    data = sys.stdin.read().split()  
    n = int(data[0])
    m = int(data[1])
    G = []
    index = 2
    
    for _ in range(m):
        u = int(data[index]) - 1
        v = int(data[index + 1]) - 1
        c = int(data[index + 2]) - 1
        index += 3
        G.append((c, u, v))
    
    G.sort()
    parent = list(range(n))
    rank = [0] * n
    cnt = [0] * 6
    
    for c, u, v in G:
        if find(parent, u) != find(parent, v):
            cnt[c] += 1
            union(parent, rank, u, v)
    
    zero = tuple([0] * 6)
    
    @lru_cache(None)
    def solve(cond):
        if cond == zero:
            return 0.0
        MAX = -1
        ng = 0
        total = 0.0
        cond = list(cond)
        
        for i in range(6):
            if cond[i] > 0:
                MAX = i
            if MAX >= 0:
                cond[MAX] -= 1
                total += solve(tuple(cond))
                cond[MAX] += 1
            else:
                ng += 1
        
        assert ng < 6
        return (total + 6) / (6 - ng)
    
    print(f"{solve(tuple(cnt)):.15f}")

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