結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー guricerin
提出日時 2020-01-31 22:54:17
言語 F#
(F# 4.0)
結果
WA  
実行時間 -
コード長 2,064 bytes
コンパイル時間 12,414 ms
コンパイル使用メモリ 200,700 KB
実行使用メモリ 48,768 KB
最終ジャッジ日時 2024-09-17 09:54:12
合計ジャッジ時間 15,561 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (236 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.fs(61,13): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

open System
open System.Collections.Generic

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f
    let readChars() = read string |> Seq.toArray
    let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

[<AutoOpen>]
module Cout =
    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let print (s: string) = writer.Write s
    let println (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> println

type UnionFind =
    { par: int array
      rank: int array }

[<RequireQualifiedAccess>]
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module UnionFind =

    let inline init (n: ^a) =
        let n = int n
        let par = Array.init n id
        let rank = Array.zeroCreate n
        { UnionFind.par = par
          rank = rank }

    let rec root x uf =
        let par = uf.par
        match x = par.[x] with
        | true -> x
        | false ->
            let px = par.[x]
            par.[x] <- root px uf
            par.[x]

    let find x y uf = (root x uf) = (root y uf)

    let unite x y uf =
        let par, rank = uf.par, uf.rank
        let rx, ry = root x uf, root y uf
        match rx = ry with
        | true -> false
        | false ->
            let large, small =
                if rank.[rx] < rank.[ry] then ry, rx else rx, ry
            par.[small] <- large
            rank.[large] <- rank.[large] + rank.[small]
            rank.[small] <- 0
            true

let main() =
    let n = read int
    let uni = UnionFind.init n
    for i in 0 .. n - 2 do
        let [| u; v |] = reada int
        uni
        |> UnionFind.unite u v
        |> ignore

    let o = uni |> UnionFind.root (n - 1)
    let cnt = Array.filter (fun i -> (UnionFind.root i uni) <> o) uni.par |> Array.length
    // let ok = Array.forall (fun i -> UnionFind.root i uni = o) uni.par
    if cnt < 2 then "Bob" else "Alice"
    |> puts
    ()

main()
writer.Close()
0