結果

問題 No.2584 The University of Tree
ユーザー hirayuu_ychirayuu_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
54,144 KB
testcase_01 AC 46 ms
60,032 KB
testcase_02 AC 41 ms
54,016 KB
testcase_03 AC 41 ms
54,272 KB
testcase_04 AC 112 ms
77,752 KB
testcase_05 AC 101 ms
76,928 KB
testcase_06 AC 108 ms
77,184 KB
testcase_07 AC 103 ms
77,208 KB
testcase_08 AC 109 ms
77,568 KB
testcase_09 AC 103 ms
77,312 KB
testcase_10 AC 110 ms
77,056 KB
testcase_11 AC 102 ms
76,928 KB
testcase_12 AC 103 ms
77,280 KB
testcase_13 AC 102 ms
77,056 KB
testcase_14 AC 103 ms
77,056 KB
testcase_15 AC 110 ms
77,256 KB
testcase_16 AC 101 ms
77,352 KB
testcase_17 AC 103 ms
77,184 KB
testcase_18 AC 104 ms
77,056 KB
testcase_19 AC 101 ms
77,568 KB
testcase_20 AC 99 ms
77,056 KB
testcase_21 AC 102 ms
77,312 KB
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
権限があれば一括ダウンロードができます

ソースコード

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