結果

問題 No.2531 Coloring Vertices on Namori
ユーザー hirayuu_ychirayuu_yc
提出日時 2023-11-21 14:07:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 795 ms / 2,000 ms
コード長 2,111 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 198,940 KB
最終ジャッジ日時 2024-09-26 07:09:34
合計ジャッジ時間 18,813 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
54,504 KB
testcase_01 AC 40 ms
55,004 KB
testcase_02 AC 37 ms
55,128 KB
testcase_03 AC 37 ms
55,012 KB
testcase_04 AC 39 ms
54,504 KB
testcase_05 AC 401 ms
197,124 KB
testcase_06 AC 39 ms
54,740 KB
testcase_07 AC 399 ms
198,152 KB
testcase_08 AC 748 ms
198,940 KB
testcase_09 AC 778 ms
196,644 KB
testcase_10 AC 761 ms
196,628 KB
testcase_11 AC 397 ms
195,000 KB
testcase_12 AC 406 ms
196,024 KB
testcase_13 AC 422 ms
195,892 KB
testcase_14 AC 589 ms
196,060 KB
testcase_15 AC 599 ms
196,356 KB
testcase_16 AC 605 ms
196,296 KB
testcase_17 AC 38 ms
54,016 KB
testcase_18 AC 37 ms
54,144 KB
testcase_19 AC 38 ms
54,272 KB
testcase_20 AC 651 ms
171,800 KB
testcase_21 AC 647 ms
171,948 KB
testcase_22 AC 642 ms
170,380 KB
testcase_23 AC 644 ms
170,484 KB
testcase_24 AC 668 ms
172,076 KB
testcase_25 AC 650 ms
171,668 KB
testcase_26 AC 781 ms
170,288 KB
testcase_27 AC 795 ms
171,704 KB
testcase_28 AC 639 ms
170,284 KB
testcase_29 AC 631 ms
171,448 KB
testcase_30 AC 680 ms
170,924 KB
testcase_31 AC 657 ms
172,208 KB
testcase_32 AC 667 ms
171,812 KB
testcase_33 AC 664 ms
171,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353
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]
    
    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
def bridge(gr):
    pre=[-1]*gr.size
    low=[-1]*gr.size
    ret=[]
    for i in range(gr.size):
        if pre[i]!=-1:
            continue
        vert=deque([[0,i,-1,-1]])
        cnt=0
        while len(vert)>0:
            step,now,bef,ed=vert[-1]
            if step==1:
                for j in gr.node(now):
                    if j.to!=bef:
                        low[now]=min(low[now],low[j.to])
                if ed!=-1 and pre[now]<=low[now]:
                    ret.append(gr.node(bef)[ed])
                vert.pop()
                continue
            if pre[now]!=-1:
                low[bef]=min(low[bef],low[now])
                vert.pop()
                continue
            pre[now]=cnt
            low[now]=cnt
            cnt+=1
            vert[-1][0]=1
            for j,k in enumerate(gr.node(now)):
                if k.to==bef:
                    continue
                if low[k.to]==-1:
                    vert.append([0,k.to,now,j])
                else:
                    low[now]=min(low[now],low[k.to])
    return ret

N,K=map(int,input().split())
namori=Graph(N)
for i in range(N):
    u,v=map(int,input().split())
    namori.add_edge(u-1,v-1)
cycle=N-len(bridge(namori))
dp=[[0,0] for i in range(cycle)]
dp[0][0]=K
for i in range(cycle-1):
    dp[i+1][0]=dp[i][1]
    dp[i+1][1]=(dp[i][0]*(K-1)+dp[i][1]*(K-2))%MOD
print((dp[-1][1]*pow(K-1,N-cycle,MOD))%MOD)
0