#565838 (Crystal) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	yuruhiya
提出日時	2020-10-11 12:59:54
言語	Crystal (1.11.2)
結果	AC
実行時間	140 ms / 2,000 ms
コード長	1,106 bytes
コンパイル時間	21,046 ms
コンパイル使用メモリ	257,476 KB
実行使用メモリ	33,972 KB
最終ジャッジ日時	2023-09-13 12:13:42
合計ジャッジ時間	33,530 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,432 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	2 ms 4,392 KB
testcase_05	AC	3 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	3 ms 4,404 KB
testcase_11	AC	2 ms 4,420 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,396 KB
testcase_14	AC	2 ms 4,444 KB
testcase_15	AC	3 ms 4,440 KB
testcase_16	AC	2 ms 4,468 KB
testcase_17	AC	2 ms 4,400 KB
testcase_18	AC	2 ms 4,428 KB
testcase_19	AC	2 ms 4,404 KB
testcase_20	AC	3 ms 4,432 KB
testcase_21	AC	3 ms 4,380 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,456 KB
testcase_24	AC	3 ms 4,504 KB
testcase_25	AC	3 ms 4,380 KB
testcase_26	AC	2 ms 4,376 KB
testcase_27	AC	3 ms 4,468 KB
testcase_28	AC	2 ms 4,472 KB
testcase_29	AC	3 ms 4,432 KB
testcase_30	AC	3 ms 4,496 KB
testcase_31	AC	2 ms 4,436 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	2 ms 4,380 KB
testcase_34	AC	3 ms 4,508 KB
testcase_35	AC	3 ms 4,516 KB
testcase_36	AC	3 ms 4,520 KB
testcase_37	AC	3 ms 4,380 KB
testcase_38	AC	3 ms 4,452 KB
testcase_39	AC	3 ms 4,452 KB
testcase_40	AC	3 ms 4,444 KB
testcase_41	AC	2 ms 4,384 KB
testcase_42	AC	2 ms 4,384 KB
testcase_43	AC	4 ms 4,632 KB
testcase_44	AC	3 ms 4,568 KB
testcase_45	AC	2 ms 4,488 KB
testcase_46	AC	3 ms 4,680 KB
testcase_47	AC	3 ms 4,556 KB
testcase_48	AC	3 ms 4,632 KB
testcase_49	AC	3 ms 4,452 KB
testcase_50	AC	3 ms 4,716 KB
testcase_51	AC	3 ms 4,720 KB
testcase_52	AC	3 ms 4,656 KB
testcase_53	AC	3 ms 4,608 KB
testcase_54	AC	3 ms 4,656 KB
testcase_55	AC	3 ms 4,720 KB
testcase_56	AC	2 ms 4,544 KB
testcase_57	AC	3 ms 4,660 KB
testcase_58	AC	3 ms 4,632 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	3 ms 4,524 KB
testcase_61	AC	3 ms 4,700 KB
testcase_62	AC	2 ms 4,424 KB
testcase_63	AC	9 ms 6,576 KB
testcase_64	AC	4 ms 4,936 KB
testcase_65	AC	7 ms 5,704 KB
testcase_66	AC	6 ms 5,484 KB
testcase_67	AC	4 ms 4,928 KB
testcase_68	AC	6 ms 5,504 KB
testcase_69	AC	7 ms 5,904 KB
testcase_70	AC	4 ms 5,120 KB
testcase_71	AC	4 ms 4,920 KB
testcase_72	AC	7 ms 5,972 KB
testcase_73	AC	4 ms 5,024 KB
testcase_74	AC	7 ms 5,792 KB
testcase_75	AC	6 ms 5,660 KB
testcase_76	AC	3 ms 4,720 KB
testcase_77	AC	5 ms 5,524 KB
testcase_78	AC	8 ms 6,384 KB
testcase_79	AC	8 ms 6,344 KB
testcase_80	AC	7 ms 6,080 KB
testcase_81	AC	8 ms 6,484 KB
testcase_82	AC	8 ms 6,328 KB
testcase_83	AC	87 ms 22,308 KB
testcase_84	AC	82 ms 22,968 KB
testcase_85	AC	40 ms 14,972 KB
testcase_86	AC	69 ms 20,912 KB
testcase_87	AC	75 ms 23,328 KB
testcase_88	AC	12 ms 7,320 KB
testcase_89	AC	79 ms 22,276 KB
testcase_90	AC	45 ms 15,940 KB
testcase_91	AC	36 ms 13,428 KB
testcase_92	AC	20 ms 9,820 KB
testcase_93	AC	61 ms 19,548 KB
testcase_94	AC	50 ms 17,732 KB
testcase_95	AC	51 ms 17,528 KB
testcase_96	AC	77 ms 22,944 KB
testcase_97	AC	31 ms 14,100 KB
testcase_98	AC	76 ms 23,052 KB
testcase_99	AC	40 ms 14,456 KB
testcase_100	AC	74 ms 23,584 KB
testcase_101	AC	17 ms 8,712 KB
testcase_102	AC	9 ms 6,684 KB
testcase_103	AC	21 ms 9,500 KB
testcase_104	AC	23 ms 11,200 KB
testcase_105	AC	56 ms 19,988 KB
testcase_106	AC	31 ms 13,220 KB
testcase_107	AC	77 ms 22,892 KB
testcase_108	AC	72 ms 22,768 KB
testcase_109	AC	57 ms 19,236 KB
testcase_110	AC	43 ms 17,320 KB
testcase_111	AC	55 ms 18,756 KB
testcase_112	AC	24 ms 10,668 KB
testcase_113	AC	44 ms 16,720 KB
testcase_114	AC	31 ms 13,068 KB
testcase_115	AC	12 ms 7,264 KB
testcase_116	AC	36 ms 13,556 KB
testcase_117	AC	24 ms 10,636 KB
testcase_118	AC	66 ms 21,856 KB
testcase_119	AC	40 ms 14,420 KB
testcase_120	AC	71 ms 22,380 KB
testcase_121	AC	21 ms 10,116 KB
testcase_122	AC	33 ms 13,532 KB
testcase_123	AC	2 ms 4,380 KB
testcase_124	AC	140 ms 33,972 KB
testcase_125	AC	137 ms 33,832 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

lib C
  fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64
end

class String
  def to_i64
    C.strtoll(self, nil, 10)
  end
end

class Solve
  @n : Int32
  @g = Array(Array(Tuple(Int32, Int32))).new
  @edges = [] of Tuple(Int32, Int32)
  @in_loop : Int32?

  def initialize
    @n = read_line.to_i
    @g = (1..@n).map { Array(Tuple(Int32, Int32)).new }
    @n.times do |i|
      a, b = read_line.split.map(&.to_i.pred)
      @g[a] << {b, i}
      @g[b] << {a, i}
      @edges << {a, b}
    end
    @flag = Array(Int32?).new(@n, nil)
  end

  def dfs(v, prev, prev_edge)
    if @flag[v]
      @in_loop = v
      @flag[v] = prev_edge
      return
    end
    @flag[v] = prev_edge
    @g[v].each do |(u, i)|
      next if u == prev || @in_loop
      dfs(u, v, i)
    end
  end

  def solve
    dfs(0, -1, -1)
    ans = [] of Int32
    now = @in_loop.not_nil!
    while now != @in_loop || ans.empty?
      edge_i = @flag[now].not_nil!
      ans << edge_i + 1
      u, v = @edges[edge_i]
      now = u == now ? v : u
    end
    puts ans.size, ans.sort.join(' ')
  end
end

solve = Solve.new
solve.solve

yukicoder

結果

テストケース

ソースコード