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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	yuruhiya
提出日時	2020-10-11 12:59:54
言語	Crystal (1.11.2)
結果	AC
実行時間	133 ms / 2,000 ms
コード長	1,106 bytes
コンパイル時間	11,754 ms
コンパイル使用メモリ	297,568 KB
実行使用メモリ	27,100 KB
最終ジャッジ日時	2024-06-30 21:20:10
合計ジャッジ時間	23,087 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	2 ms 6,944 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,940 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,944 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	3 ms 6,940 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	3 ms 6,944 KB
testcase_47	AC	2 ms 6,944 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	2 ms 6,940 KB
testcase_50	AC	2 ms 6,944 KB
testcase_51	AC	2 ms 6,944 KB
testcase_52	AC	3 ms 6,940 KB
testcase_53	AC	3 ms 6,944 KB
testcase_54	AC	2 ms 6,940 KB
testcase_55	AC	2 ms 6,944 KB
testcase_56	AC	2 ms 6,944 KB
testcase_57	AC	2 ms 6,940 KB
testcase_58	AC	3 ms 6,944 KB
testcase_59	AC	2 ms 6,944 KB
testcase_60	AC	2 ms 6,940 KB
testcase_61	AC	2 ms 6,944 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	8 ms 6,940 KB
testcase_64	AC	3 ms 6,944 KB
testcase_65	AC	6 ms 6,940 KB
testcase_66	AC	5 ms 6,940 KB
testcase_67	AC	3 ms 6,944 KB
testcase_68	AC	5 ms 6,940 KB
testcase_69	AC	7 ms 6,940 KB
testcase_70	AC	5 ms 6,940 KB
testcase_71	AC	3 ms 6,940 KB
testcase_72	AC	7 ms 6,944 KB
testcase_73	AC	3 ms 6,940 KB
testcase_74	AC	6 ms 6,940 KB
testcase_75	AC	5 ms 6,944 KB
testcase_76	AC	3 ms 6,940 KB
testcase_77	AC	5 ms 6,940 KB
testcase_78	AC	7 ms 6,940 KB
testcase_79	AC	7 ms 6,940 KB
testcase_80	AC	7 ms 6,940 KB
testcase_81	AC	7 ms 6,940 KB
testcase_82	AC	7 ms 6,944 KB
testcase_83	AC	86 ms 20,188 KB
testcase_84	AC	73 ms 20,824 KB
testcase_85	AC	39 ms 14,076 KB
testcase_86	AC	62 ms 17,192 KB
testcase_87	AC	64 ms 19,068 KB
testcase_88	AC	11 ms 6,944 KB
testcase_89	AC	74 ms 20,312 KB
testcase_90	AC	45 ms 15,052 KB
testcase_91	AC	37 ms 11,904 KB
testcase_92	AC	19 ms 7,680 KB
testcase_93	AC	58 ms 17,500 KB
testcase_94	AC	53 ms 15,424 KB
testcase_95	AC	51 ms 15,408 KB
testcase_96	AC	75 ms 19,668 KB
testcase_97	AC	30 ms 11,008 KB
testcase_98	AC	70 ms 18,996 KB
testcase_99	AC	41 ms 13,996 KB
testcase_100	AC	69 ms 20,320 KB
testcase_101	AC	17 ms 7,168 KB
testcase_102	AC	10 ms 6,940 KB
testcase_103	AC	18 ms 7,424 KB
testcase_104	AC	25 ms 9,728 KB
testcase_105	AC	58 ms 17,616 KB
testcase_106	AC	33 ms 11,648 KB
testcase_107	AC	72 ms 20,008 KB
testcase_108	AC	76 ms 20,024 KB
testcase_109	AC	58 ms 16,256 KB
testcase_110	AC	50 ms 15,360 KB
testcase_111	AC	58 ms 16,308 KB
testcase_112	AC	25 ms 11,296 KB
testcase_113	AC	51 ms 15,812 KB
testcase_114	AC	31 ms 12,600 KB
testcase_115	AC	12 ms 6,940 KB
testcase_116	AC	41 ms 12,288 KB
testcase_117	AC	25 ms 9,728 KB
testcase_118	AC	63 ms 18,596 KB
testcase_119	AC	41 ms 14,052 KB
testcase_120	AC	65 ms 18,416 KB
testcase_121	AC	21 ms 7,936 KB
testcase_122	AC	36 ms 12,160 KB
testcase_123	AC	2 ms 6,940 KB
testcase_124	AC	133 ms 27,096 KB
testcase_125	AC	122 ms 27,100 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

結果

テストケース

ソースコード