結果

問題 No.2588 Increasing Record
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-11-24 03:53:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,512 bytes
コンパイル時間 502 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 245,944 KB
最終ジャッジ日時 2024-09-27 06:38:32
合計ジャッジ時間 28,114 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,352 KB
testcase_01 AC 37 ms
52,224 KB
testcase_02 AC 37 ms
52,096 KB
testcase_03 AC 38 ms
52,352 KB
testcase_04 AC 37 ms
52,196 KB
testcase_05 AC 36 ms
52,224 KB
testcase_06 AC 37 ms
52,352 KB
testcase_07 AC 37 ms
52,224 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 211 ms
86,400 KB
testcase_13 AC 216 ms
87,552 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 560 ms
135,504 KB
testcase_31 AC 654 ms
162,308 KB
testcase_32 AC 735 ms
187,888 KB
testcase_33 AC 750 ms
191,928 KB
testcase_34 AC 746 ms
191,868 KB
testcase_35 AC 755 ms
191,712 KB
testcase_36 AC 765 ms
191,696 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 687 ms
201,748 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

連結成分ごとに場合の数を持っておけばいい？
違うな…

dp[v] = vで終わっているrecordの数
dp2[v] = 頂点vに居るときのrecordの数

新しい頂点vを追加する時…
繋がっている連結成分の頂点uに関して、u以上で終わっているrecordの数の合計を出せばok?

mergeと全体加算？


------提出後更新------

4 4
1 3
3 2
1 4
2 4
がだめでした

大きい方じゃなくて、小さい方の和を持っておくといける？
    

???
もしかして部分永続ufが必要ですか？？

"""

import sys
from sys import stdin

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        #print (dp2,"start",foot)
        if size[ap] > size[bp]:
            p[bp] = ap
            size[ap] += size[bp]
            for v in rev[bp]:
                rev[ap].add(v)
                dp2[v] = (dp2[v] + foot[bp] - foot[ap]) % mod
        else:
            p[ap] = bp
            size[bp] += size[ap]
            for v in rev[ap]:
                rev[bp].add(v)
                dp2[v] = (dp2[v] + foot[ap] - foot[bp]) % mod

        #print (dp2,"end",foot)
        #part_max[ap] = part_max[bp] = max(part_max[ap] = part_max[bp])

        return False

N,M = map(int,stdin.readline().split())

lis = [ [] for i in range(N) ]

for i in range(M):

    u,v = map(int,stdin.readline().split())
    u -= 1
    v -= 1

    lis[u].append(v)
    lis[v].append(u)

p = [i for i in range(N)]
size = [1] * N
rev = [ set([i]) for i in range(N) ]

#part_max = [i for i in range(N)]

dp  = [1] * N
dp2 = [0] * N
foot = [0] * N
mod = 998244353

for v in range(N):

    p2u = {}
    
    for u in lis[v]:
        if u < v:
            p_of_u = uf_find(u,p)
            if p_of_u not in p2u:
                p2u[p_of_u] = u
            p2u[p_of_u] = min(p2u[p_of_u] , u)

    for p_of_u in p2u:
        dp[v] += dp2[p2u[p_of_u]] + foot[p_of_u]
    dp[v] %= mod

    # merge
    for u in lis[v]:

        if u < v:
            vp = uf_find(u,p)
            up = uf_find(v,p)
            if vp != up:
                uf_union(up,vp)

    allp = uf_find(v,p)
    foot[allp] += dp[v]
    foot[allp] %= mod

    #print (dp,dp2,foot,rev)
    
for i in range(N):
    ip = uf_find(i,p)
    #print (i+1,(dp2[i] + foot[ip]) % mod)

print (sum(dp) % mod)
0