Submission #3228067
Source Code Expand
module WeightedDirectedGraph (Vertex : sig type t val compare : t -> t -> int end) (Weight : sig type t val zero : t val ( + ) : t -> t -> t val compare : t -> t -> int end) : sig val dijkstra : (* 隣接リスト *) (Vertex.t -> (Vertex.t * Weight.t) list) -> (* 始点 *) Vertex.t -> (* 始点から辿り着けなければNoneを返す *) (Vertex.t -> Weight.t option) end = struct module WMap = Map.Make (Weight) module VMap = Map.Make (Vertex) let dijkstra e s = (* 始点sからの距離 *) (* d に入っていない頂点への距離は無限大とみなす *) let d = ref @@ VMap.singleton s Weight.zero in (* 優先度付きキュー *) let q = ref @@ WMap.singleton Weight.zero [s] in (* ダイクストラ法のメインループ *) let rec dijkstra_aux t = let ans = (* AtCoderのOCaml処理系は4.02.3なので,find_optが使えない *) try Some (VMap.find t !d) with Not_found -> None in match WMap.min_binding !q with | exception Not_found -> ans | (w, us) -> if (* 現時点で終点までの距離が分かっているか *) match ans with | None -> false | Some x -> Weight.compare x w <= 0 (* 既に終点までの距離が分かっているので返す *) then ans else begin (* 終点までの距離が分かっていないので,ダイクストラ法を続行 *) q := WMap.remove w !q; List.iter (fun u -> if 0 <= Weight.compare (VMap.find u !d) w then (* 未だ頂点uを訪れていない *) List.iter (fun (v, c) -> let open Weight in if try 0 < Weight.compare (VMap.find v !d) (w + c) with Not_found -> true (* d.(v) は無限大 *) then begin d := VMap.add v (w + c) !d; q := WMap.add (w + c) (v :: try WMap.find (w + c) !q with Not_found -> []) !q end) (e u)) us; dijkstra_aux t end in dijkstra_aux end module Int = struct type t = int let zero = 0 let ( + ) = ( + ) let compare = compare end module G = WeightedDirectedGraph (Int) (Int) let val_of (Some x) = x let ( @. ) f g x = f (g x) let rec lower_bound l r p = if r <= 1 + l then r else let m = (l + r) / 2 in if p m then lower_bound l m p else lower_bound m r p let () = Scanf.scanf "%d %d %d %d\n" @@ fun n m r t -> let es = Array.make n [] in for i = 0 to m - 1 do Scanf.scanf "%d %d %d\n" @@ fun a b c -> es.(a - 1) <- (b - 1, c) :: es.(a - 1); es.(b - 1) <- (a - 1, c) :: es.(b - 1) done; Printf.printf "%d\n" @@ Array.fold_left ( + ) 0 @@ Array.init n @@ fun g -> let d = Array.init n @@ val_of @. G.dijkstra (Array.get es) g in d.(g) <- 1000000000000000; Array.sort compare d; Array.fold_left ( + ) 0 @@ Array.init (n - 1) @@ fun i -> ( - ) (n - 1 - if r < t then 1 else 0) @@ lower_bound (-1) (n - 1) @@ fun j -> d.(i) * r < d.(j) * t
Submission Info
Submission Time | |
---|---|
Task | C - ウサギとカメ |
User | fetburner |
Language | OCaml (4.02.3) |
Score | 0 |
Code Size | 3324 Byte |
Status | TLE |
Exec Time | 7356 ms |
Memory | 6912 KB |
Compile Error
File "./Main.ml", line 75, characters 11-23: Warning 8: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: None
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt |
All | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 1 ms | 384 KB |
subtask0_sample-02.txt | AC | 1 ms | 384 KB |
subtask1_01.txt | AC | 1 ms | 640 KB |
subtask1_02.txt | AC | 2 ms | 1024 KB |
subtask1_03.txt | AC | 2 ms | 1024 KB |
subtask1_04.txt | AC | 1 ms | 384 KB |
subtask1_05.txt | AC | 50 ms | 2816 KB |
subtask1_06.txt | AC | 66 ms | 2944 KB |
subtask1_07.txt | AC | 392 ms | 4224 KB |
subtask1_08.txt | AC | 381 ms | 4992 KB |
subtask1_09.txt | AC | 3422 ms | 5760 KB |
subtask1_10.txt | AC | 3278 ms | 6016 KB |
subtask1_11.txt | AC | 1413 ms | 5376 KB |
subtask1_12.txt | TLE | 7355 ms | 6016 KB |
subtask1_13.txt | TLE | 7355 ms | 6272 KB |
subtask1_14.txt | TLE | 7355 ms | 6912 KB |
subtask1_15.txt | TLE | 7355 ms | 6784 KB |
subtask1_16.txt | TLE | 7356 ms | 6912 KB |