結果

問題 No.2584 The University of Tree
コンテスト
ユーザー hirayuu_yc
提出日時 2023-11-25 17:18:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,846 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 77,752 KB
最終ジャッジ日時 2024-09-27 04:40:10
合計ジャッジ時間 9,078 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22 RE * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Graph():
    def __init__(self,size,directed=False):
        self.dir=directed
        self.size=size
        self.gr=[[] for i in range(size)]
        self.edges=[]
    
    def add_edge(self,u,v,status={}):
        self.gr[u].append(self.Edge(u,v,status))
        if not(self.dir):
            self.gr[v].append(self.Edge(v,u,status))
        self.edges.append(self.Edge(u,v,status))

    def node(self,v):
        return self.gr[v]

    def __getitem__(self,v):
        return self.gr[v]
    
    class Edge():
        def __init__(self,st,to,status):
            self.st=st
            self.to=to
            self.status=status
        
        def __getitem__(self,val):
            return self.status[val]

from collections import deque
from math import inf

def bfs(graph,start):
    dist=[inf for i in range(graph.size)]
    used=[False for i in range(graph.size)]
    dist[start]=1
    vert=deque([(1,start)])
    while len(vert)>0:
        dis,pos=vert.popleft()
        if used[pos]:
            continue
        used[pos]=True
        for i in graph.node(pos):
            if used[i.to]==False:
                vert.append((dis*i["w"]%MOD,i.to))
                dist[i.to]=dis*i["w"]%MOD
    return dist

MOD=998244353
N=int(input())
assert N<=200,"Too Large Tree!"
gr=Graph(N*3,directed=True)
cnt=[0]*(N-1)
for i in range(N):
    C,*E=list(map(int,input().split()))
    gr.add_edge(i,N+E[0]*2-2+cnt[E[0]-1],{"w":i+1})
    gr.add_edge(N+E[-1]*2-2+cnt[E[-1]-1],i,{"w":i+1})
    for j in range(C-1):
        gr.add_edge(N+E[j]*2-2+cnt[E[j]-1],N+E[j+1]*2-2+cnt[E[j+1]-1],{"w":i+1})
    for j in E:
        cnt[j-1]+=1
for i in range(N-1):
    gr.add_edge(N+i*2,N+i*2+1,{"w":1})
    gr.add_edge(N+i*2+1,N+i*2,{"w":1})
for i in range(N):
    dist=bfs(gr,i)
    ans=0
    for j in range(N):
        ans+=dist[j]
    print((ans-1)%MOD)
0