結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー guriceringuricerin
提出日時 2020-02-01 10:32:59
言語 F#
(F# 4.0)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 2,823 bytes
コンパイル時間 14,912 ms
コンパイル使用メモリ 210,420 KB
実行使用メモリ 48,540 KB
最終ジャッジ日時 2023-10-18 23:51:27
合計ジャッジ時間 19,849 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
28,896 KB
testcase_01 AC 66 ms
28,896 KB
testcase_02 AC 66 ms
28,896 KB
testcase_03 AC 66 ms
28,896 KB
testcase_04 AC 66 ms
28,904 KB
testcase_05 AC 66 ms
28,904 KB
testcase_06 AC 65 ms
28,896 KB
testcase_07 AC 66 ms
28,904 KB
testcase_08 AC 66 ms
28,912 KB
testcase_09 AC 66 ms
28,912 KB
testcase_10 AC 67 ms
28,920 KB
testcase_11 AC 66 ms
28,920 KB
testcase_12 AC 67 ms
28,920 KB
testcase_13 AC 78 ms
31,088 KB
testcase_14 AC 74 ms
31,092 KB
testcase_15 AC 74 ms
31,092 KB
testcase_16 AC 73 ms
31,096 KB
testcase_17 AC 74 ms
31,096 KB
testcase_18 AC 89 ms
35,040 KB
testcase_19 AC 89 ms
35,032 KB
testcase_20 AC 100 ms
38,560 KB
testcase_21 AC 119 ms
43,732 KB
testcase_22 AC 134 ms
47,664 KB
testcase_23 AC 141 ms
48,540 KB
testcase_24 AC 134 ms
48,540 KB
testcase_25 AC 140 ms
48,540 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (908 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
/home/judge/data/code/Main.fs(84,13): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj]
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.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