結果

問題 No.1805 Approaching Many Typhoon
ユーザー tatt61880
提出日時 2023-03-14 20:36:25
言語 Kuin
(KuinC++ v.2021.9.17)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,459 bytes
コンパイル時間 3,722 ms
コンパイル使用メモリ 149,024 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 08:23:06
合計ジャッジ時間 3,877 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

func main()
    var n: int :: cui@inputInt()
    var m: int :: cui@inputInt()
    var s: int :: cui@inputInt()
    var g: int :: cui@inputInt()
    
    var f: []int :: #[m]int
    var t: []int :: #[m]int
    for i(0, m - 1)
        do f[i] :: cui@inputInt()
        do t[i] :: cui@inputInt()
    end for
    
    var u: int :: cui@inputInt()
    var ng: dict<int, bool> :: #dict<int, bool>
    for(1, u)
        var i: int :: cui@inputInt()
        do ng.add(i, true)
    end for
    
    var uni: UnionFind :: (#UnionFind).init(n + 1)
    
    for i(0, m - 1)
        var fi: int :: f[i]
        var ti: int :: t[i]
        if(!ng.get(fi, &) & !ng.get(ti, &))
            do uni.unite(fi, ti)
        end if
    end for
    
    var ans: bool :: uni.same(s, g)
    do cui@print((ans ?("Yes", "No")) ~ "\n")
    
    class UnionFind()
        var parents: []int
        +func init(n: int): UnionFind
            do me.parents :: [-1].repeat(n)
            ret me
        end func
        +func size(x: int): int
            ret -me.parents[me.root(x)]
        end func
        +func same(x: int, y: int): bool
            ret me.root(x) = me.root(y)
        end func
        +func unite(x: int, y: int): bool
            do x :: me.root(x)
            do y :: me.root(y)
            if(x = y)
                ret false
            end if
            if(me.size(x) < me.size(y))
                do me.parents[y] :+ me.parents[x]
                do me.parents[x] :: y
            else
                do me.parents[x] :+ me.parents[y]
                do me.parents[y] :: x
            end if
            ret true
        end func
        
        func root(x: int): int
            if(me.parents[x] < 0)
                ret x
            else
                do me.parents[x] :: me.root(me.parents[x])
                ret me.parents[x]
            end if
        end func
    end class
end func
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0