結果

問題 No.3079 Unite Japanese Prefectures
コンテスト
ユーザー ゼット
提出日時 2025-03-28 22:38:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 560 ms / 4,000 ms
コード長 1,788 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 91,384 KB
最終ジャッジ日時 2025-03-28 22:38:54
合計ジャッジ時間 7,205 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

class unif:
  def __init__(self,n):
    self.pare=[-1]*n
    self.size=[1]*n
  def root(self,x):
    while self.pare[x]!=-1:
      x=self.pare[x]
    return x
  def unite(self,u,v):
    rootu=self.root(u)
    rootv=self.root(v)
    if rootu!=rootv:
      if self.size[rootu]>=self.size[rootv]:
        self.pare[rootv]=rootu
        self.size[rootu]+=self.size[rootv]
      else:
        self.pare[rootu]=rootv
        self.size[rootv]+=self.size[rootu]
  def same(self,s,t):
    return self.root(s)==self.root(t)
N,M=map(int,input().split())
u=[0]*7
L=[]
Z=unif(N)
for i in range(M):
  a,b,c=map(int,input().split())
  L.append((c,a-1,b-1))
L.sort()
for i in range(M):
  c,a,b=L[i][:]
  if Z.same(a,b)==False:
    u[c]+=1
    Z.unite(a,b)
R=[]
for k in range(1,7):
  for i in range((u[k])):
    R.append(k)
K=len(R)
a,b,c,d,e,f=u[1],u[2],u[3],u[4],u[5],u[6]
dp=[[[[[[0]*(f+1) for i in range(e+1)] for j in range(d+1)] for k in range(c+1)] for l in range(b+1)] for r in range(a+1)]
for c1 in range(a+1):
  for c2 in range(b+1):
    for c3 in range(c+1):
      for c4 in range(d+1):
        for c5 in range(e+1):
          for c6 in range(f+1):
            v=[0,c1,c2,c3,c4,c5,c6]
            if sum(v)==0:
              continue
            w=1
            t=0
            for x in range(1,7):
              ans=False
              for y in range(x,0,-1):
                if v[y]==0:
                  continue
                v2=v[:]
                v2[y]-=1
                v2=v2[1:]
                z1,z2,z3,z4,z5,z6=v2[:]
                score=dp[z1][z2][z3][z4][z5][z6]
                w+=score/6
                ans=True
                break
              if ans==False:
                t+=1/6
            w/=1-t
            dp[c1][c2][c3][c4][c5][c6]=w
print(dp[a][b][c][d][e][f])
0