結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー guriceringuricerin
提出日時 2020-01-31 22:22:00
言語 F#
(F# 4.0)
結果
WA  
実行時間 -
コード長 1,960 bytes
コンパイル時間 17,418 ms
コンパイル使用メモリ 207,688 KB
実行使用メモリ 50,032 KB
最終ジャッジ日時 2023-10-17 10:21:00
合計ジャッジ時間 16,183 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
30,808 KB
testcase_01 AC 60 ms
30,808 KB
testcase_02 AC 59 ms
30,808 KB
testcase_03 AC 59 ms
30,808 KB
testcase_04 AC 58 ms
30,808 KB
testcase_05 AC 59 ms
30,808 KB
testcase_06 AC 59 ms
30,808 KB
testcase_07 AC 59 ms
30,816 KB
testcase_08 AC 61 ms
30,824 KB
testcase_09 AC 61 ms
30,824 KB
testcase_10 WA -
testcase_11 AC 60 ms
30,824 KB
testcase_12 AC 59 ms
30,824 KB
testcase_13 AC 93 ms
32,920 KB
testcase_14 AC 67 ms
32,920 KB
testcase_15 AC 66 ms
32,920 KB
testcase_16 AC 68 ms
32,920 KB
testcase_17 AC 66 ms
32,920 KB
testcase_18 AC 81 ms
36,800 KB
testcase_19 WA -
testcase_20 AC 91 ms
40,256 KB
testcase_21 AC 108 ms
45,324 KB
testcase_22 AC 119 ms
49,172 KB
testcase_23 AC 130 ms
50,032 KB
testcase_24 AC 126 ms
50,032 KB
testcase_25 AC 130 ms
50,032 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.fsproj を復元しました (640 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
/home/judge/data/code/Main.fs(61,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 =
    { 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 0
    let ok = Array.forall (fun i -> UnionFind.root i uni = o) uni.par
    if ok then "Bob" else "Alice"
    |> puts
    ()

main()
writer.Close()
0