結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー guricerin
提出日時 2020-02-01 10:32:59
言語 F#
(F# 4.0)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 2,823 bytes
コンパイル時間 12,440 ms
コンパイル使用メモリ 202,804 KB
実行使用メモリ 49,280 KB
最終ジャッジ日時 2024-09-18 19:48:20
合計ジャッジ時間 15,689 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (456 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
/home/judge/data/code/Main.fs(84,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 =
    {
      /// 添字iが属するグループID
      par: int array
      /// 各集合の要素数
      size: int array }

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

    /// O(n)
    let init (n: int): UnionFind =
        let par = Array.init n id
        let size = Array.init n (fun _ -> 1)
        { UnionFind.par = par
          size = size }

    /// x: 0-indexed
    let rec root (x: int) (uf: UnionFind): int =
        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: int) (y: int) (uf: UnionFind) = (root x uf) = (root y uf)

    let unite (x: int) (y: int) (uf: UnionFind): bool =
        let par, size = uf.par, uf.size
        let rx, ry = root x uf, root y uf
        match rx = ry with
        | true -> false
        | _ ->
            // マージテク(大きい方に小さい方を併合)
            let large, small =
                if size.[rx] < size.[ry] then ry, rx else rx, ry
            par.[small] <- large
            size.[large] <- size.[large] + size.[small]
            size.[small] <- 0
            true

    /// 素集合のサイズ
    /// x: 0-indexed
    let size (x: int) (uf: UnionFind): int =
        let rx = root x uf
        uf.size.[rx]

    /// 連結成分の個数
    /// O(n)
    let treeNum (uf: UnionFind): int =
        let par = uf.par
        let mutable cnt = 0
        par
        |> Array.iteri (fun i x ->
            if i = x then cnt <- cnt + 1)
        cnt

let main() =
    let n = read int
    let uf = UnionFind.init n
    let degs = Array.zeroCreate n
    for i in 0 .. n - 2 do
        let [| u; v |] = reada int
        UnionFind.unite u v uf |> ignore
        degs.[u] <- degs.[u] + 1
        degs.[v] <- degs.[v] + 1

    let num = uf |> UnionFind.treeNum
    let A = "Alice"
    let B = "Bob"
    if num >= 3 then
        A
    elif num = 2 then
        let ok = degs |> Array.tryFind (fun x -> x = 1)
        match ok with
        | Some _ -> A
        | _ -> B
    else
        B
    |> puts
    ()

main()
writer.Close()
0