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
AC × 2
AC × 13
TLE × 5
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