AtCoder Beginner Contest 035

Submission #676838

Source codeソースコード

let rec tabulate n f = 
  let rec loop acc m =
    if m < n then loop (f m :: acc) (m + 1)
    else List.rev acc in
  loop [] 0

let make_edge n abcs =
  let edge = Array.make n [] in
  List.iter (fun (a, b, c) ->
    edge.(a) <- (b, c) :: edge.(a)) abcs;
  edge

let rec dikjstra ( +. ) q edge d =
  match q with
  | [] -> ()
  | u :: q ->
      let u, q = 
        List.fold_left (fun (u, q') u' ->
          if d.(u) < d.(u') then (u, u' :: q') else (u', u :: q')) (u, []) q in
      List.iter (fun (v, c) ->
        d.(v) <- min d.(v) (d.(u) +. c)) edge.(u);
      dikjstra ( +. ) q edge d

let () =
  let n, m, t = Scanf.scanf "%d %d %d\n" (fun n m t -> n, m, t) in
  let as_ = Array.init n (fun _ -> Scanf.scanf "%d " (fun a -> a)) in
  let abcs = tabulate m (fun _ ->
    Scanf.scanf "%d %d %d\n" (fun a b c -> a - 1, b - 1, c)) in
  let d = Array.make n 1145141919 in
  d.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i)) (make_edge n abcs) d;
  let d' = Array.make n 1145141919 in
  d'.(0) <- 0;
  dikjstra ( + ) (tabulate n (fun i -> i))
    (make_edge n (List.map (fun (a, b, c) -> (b, a, c)) abcs)) d';
  tabulate n (fun i ->
    as_.(i) * (t - d.(i) - d'.(i)))
  |> List.fold_left max 0
  |> Printf.printf "%d\n"

Submission

Task問題 D - トレジャーハント
User nameユーザ名 launderer
Created time投稿日時
Language言語 OCaml (4.02.3)
Status状態 TLE
Score得点 50
Source lengthソースコード長 1268 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
Subtask1 50 / 50 00_example_01.txt,00_example_02.txt,00_example_03.txt,50_small_01.txt,50_small_02.txt,50_small_03.txt,50_small_04.txt,50_small_05.txt,50_small_06.txt,50_small_07.txt,50_small_08.txt,50_small_09.txt,50_small_10.txt,60_hand_01.txt,60_hand_02.txt,60_hand_03.txt,60_hand_04.txt,70_max_01.txt,70_max_02.txt,70_max_03.txt
All 0 / 50 00_example_01.txt,00_example_02.txt,00_example_03.txt,10_rand_01.txt,10_rand_02.txt,10_rand_03.txt,10_rand_04.txt,10_rand_05.txt,10_rand_06.txt,10_rand_07.txt,10_rand_08.txt,10_rand_09.txt,10_rand_10.txt,10_rand_12.txt,10_rand_13.txt,30_max_01.txt,30_max_02.txt,30_max_03.txt,30_max_04.txt,30_max_05.txt,30_max_06.txt,40_corner_01.txt,40_corner_02.txt,40_corner_03.txt,40_corner_04.txt,50_small_01.txt,50_small_02.txt,50_small_03.txt,50_small_04.txt,50_small_05.txt,50_small_06.txt,50_small_07.txt,50_small_08.txt,50_small_09.txt,50_small_10.txt,60_hand_01.txt,60_hand_02.txt,60_hand_03.txt,60_hand_04.txt,70_max_01.txt,70_max_02.txt,70_max_03.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 4 ms 384 KB
00_example_02.txt AC 4 ms 384 KB
00_example_03.txt AC 4 ms 384 KB
10_rand_01.txt TLE
10_rand_02.txt TLE
10_rand_03.txt TLE
10_rand_04.txt TLE
10_rand_05.txt TLE
10_rand_06.txt TLE
10_rand_07.txt TLE
10_rand_08.txt TLE
10_rand_09.txt TLE
10_rand_10.txt TLE
10_rand_12.txt TLE
10_rand_13.txt TLE
30_max_01.txt TLE
30_max_02.txt TLE
30_max_03.txt AC 1562 ms 30464 KB
30_max_04.txt TLE
30_max_05.txt TLE
30_max_06.txt TLE
40_corner_01.txt TLE
40_corner_02.txt TLE
40_corner_03.txt TLE
40_corner_04.txt TLE
50_small_01.txt AC 8 ms 1792 KB
50_small_02.txt AC 4 ms 512 KB
50_small_03.txt AC 6 ms 1152 KB
50_small_04.txt AC 5 ms 896 KB
50_small_05.txt AC 12 ms 2944 KB
50_small_06.txt AC 9 ms 2304 KB
50_small_07.txt AC 5 ms 1024 KB
50_small_08.txt AC 4 ms 384 KB
50_small_09.txt AC 6 ms 1152 KB
50_small_10.txt AC 5 ms 640 KB
60_hand_01.txt AC 4 ms 384 KB
60_hand_02.txt AC 4 ms 384 KB
60_hand_03.txt AC 4 ms 384 KB
60_hand_04.txt AC 4 ms 384 KB
70_max_01.txt AC 103 ms 11904 KB
70_max_02.txt AC 102 ms 11904 KB
70_max_03.txt AC 107 ms 11904 KB