結果

問題 No.2588 Increasing Record
コンテスト
ユーザー 👑 SPD_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 29
権限があれば一括ダウンロードができます

ソースコード

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