#664090 (Nim) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	dot_haraai
提出日時	2021-06-05 20:51:37
言語	Nim (2.0.2)
結果	AC
実行時間	202 ms / 2,000 ms
コード長	2,120 bytes
コンパイル時間	4,923 ms
コンパイル使用メモリ	90,056 KB
実行使用メモリ	26,336 KB
最終ジャッジ日時	2024-05-01 14:52:57
合計ジャッジ時間	18,120 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 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	1 ms 6,948 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,940 KB
testcase_22	AC	1 ms 6,944 KB
testcase_23	AC	2 ms 6,944 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	1 ms 6,948 KB
testcase_29	AC	1 ms 6,944 KB
testcase_30	AC	1 ms 6,940 KB
testcase_31	AC	1 ms 6,944 KB
testcase_32	AC	1 ms 6,940 KB
testcase_33	AC	2 ms 6,944 KB
testcase_34	AC	1 ms 6,944 KB
testcase_35	AC	1 ms 6,944 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	1 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB
testcase_42	AC	1 ms 6,944 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	2 ms 6,944 KB
testcase_47	AC	2 ms 6,944 KB
testcase_48	AC	3 ms 6,944 KB
testcase_49	AC	1 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	3 ms 6,944 KB
testcase_52	AC	3 ms 6,944 KB
testcase_53	AC	2 ms 6,940 KB
testcase_54	AC	3 ms 6,944 KB
testcase_55	AC	2 ms 6,940 KB
testcase_56	AC	1 ms 6,944 KB
testcase_57	AC	3 ms 6,940 KB
testcase_58	AC	2 ms 6,940 KB
testcase_59	AC	2 ms 6,944 KB
testcase_60	AC	2 ms 6,944 KB
testcase_61	AC	3 ms 6,944 KB
testcase_62	AC	2 ms 6,940 KB
testcase_63	AC	12 ms 6,940 KB
testcase_64	AC	4 ms 6,940 KB
testcase_65	AC	8 ms 6,940 KB
testcase_66	AC	7 ms 6,940 KB
testcase_67	AC	4 ms 6,944 KB
testcase_68	AC	7 ms 6,940 KB
testcase_69	AC	9 ms 6,940 KB
testcase_70	AC	5 ms 6,940 KB
testcase_71	AC	4 ms 6,940 KB
testcase_72	AC	10 ms 6,940 KB
testcase_73	AC	4 ms 6,940 KB
testcase_74	AC	9 ms 6,944 KB
testcase_75	AC	7 ms 6,944 KB
testcase_76	AC	3 ms 6,944 KB
testcase_77	AC	7 ms 6,940 KB
testcase_78	AC	11 ms 6,940 KB
testcase_79	AC	11 ms 6,940 KB
testcase_80	AC	10 ms 6,940 KB
testcase_81	AC	11 ms 6,944 KB
testcase_82	AC	11 ms 6,940 KB
testcase_83	AC	197 ms 18,936 KB
testcase_84	AC	171 ms 18,688 KB
testcase_85	AC	83 ms 12,800 KB
testcase_86	AC	136 ms 16,420 KB
testcase_87	AC	165 ms 17,768 KB
testcase_88	AC	18 ms 6,940 KB
testcase_89	AC	181 ms 18,808 KB
testcase_90	AC	95 ms 13,312 KB
testcase_91	AC	69 ms 11,008 KB
testcase_92	AC	33 ms 7,424 KB
testcase_93	AC	130 ms 15,744 KB
testcase_94	AC	122 ms 14,720 KB
testcase_95	AC	115 ms 14,592 KB
testcase_96	AC	166 ms 18,020 KB
testcase_97	AC	56 ms 9,984 KB
testcase_98	AC	169 ms 18,280 KB
testcase_99	AC	88 ms 12,416 KB
testcase_100	AC	192 ms 19,236 KB
testcase_101	AC	29 ms 6,940 KB
testcase_102	AC	15 ms 6,944 KB
testcase_103	AC	32 ms 7,296 KB
testcase_104	AC	44 ms 8,832 KB
testcase_105	AC	132 ms 15,744 KB
testcase_106	AC	63 ms 10,624 KB
testcase_107	AC	185 ms 18,860 KB
testcase_108	AC	167 ms 18,580 KB
testcase_109	AC	130 ms 15,616 KB
testcase_110	AC	107 ms 14,464 KB
testcase_111	AC	134 ms 15,488 KB
testcase_112	AC	44 ms 8,704 KB
testcase_113	AC	106 ms 14,080 KB
testcase_114	AC	59 ms 10,368 KB
testcase_115	AC	20 ms 6,940 KB
testcase_116	AC	72 ms 11,648 KB
testcase_117	AC	45 ms 8,576 KB
testcase_118	AC	169 ms 18,136 KB
testcase_119	AC	81 ms 12,160 KB
testcase_120	AC	162 ms 17,536 KB
testcase_121	AC	37 ms 7,808 KB
testcase_122	AC	68 ms 11,392 KB
testcase_123	AC	2 ms 6,940 KB
testcase_124	AC	202 ms 26,336 KB
testcase_125	AC	195 ms 26,124 KB

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

コンパイルメッセージ

/home/judge/data/code/Main.nim(2, 18) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'times' [UnusedImport]
/home/judge/data/code/Main.nim(2, 26) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(2, 18) Warning: imported and not used: 'future' [UnusedImport]
/home/judge/data/code/Main.nim(2, 37) Warning: imported and not used: 'deques' [UnusedImport]
/home/judge/data/code/Main.nim(1, 73) Warning: imported and not used: 'intsets' [UnusedImport]
/home/judge/data/code/Main.nim(1, 52) Warning: imported and not used: 'tables' [UnusedImport]
/home/judge/data/code/Main.nim(2, 8) Warning: imported and not used: 'critbits' [UnusedImport]
/home/judge/data/code/Main.nim(1, 66) Warning: imported and not used: 'lists' [UnusedImport]

ソースコード

raw source code

import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
template `mod=`(x,y) = x = x mod y
template scan2 = (scan(), scan())
template scan3 = (scan(), scan())
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc scanf(): float = read().parseFloat
proc toInt(c:char): int =
    return int(c) - int('0')




proc solve()=
  var
    n = scan()
    es = newseqwith(n,newseq[int]())
    
    loopE = newseqwith(n,newseq[bool]())
    invE = newseqwith(n,newseq[int]())
    ids = newseqwith(n,newseq[int]())
    touch = newseqwith(n,false)
  for i in 0..<n:
    var
      a = scan()-1
      b = scan()-1
    es[a].add(b)
    loopE[a].add(false)
    ids[a].add(i+1)
    es[b].add(a)
    loopE[b].add(false)
    ids[b].add(i+1)
    invE[a].add(es[b].len-1)
    invE[b].add(es[a].len-1)

  proc dfsFindLoop(par,p:int):int=
    result = -1
    if touch[p]:
      return p
    else:
      touch[p]=true
    for nIdx in 0..<es[p].len:
      var
        nxt = es[p][nIdx]
      if nxt == par:continue
      else:
        var t = dfsFindLoop(p,nxt)
        if t>=0:
          return t
    return -1


  proc dfs(par:int,p:int):bool=
    if touch[p]:
      return true
    else:
      touch[p]=true
    for nIdx in 0..<es[p].len:
      var
        nxt = es[p][nIdx]
      if nxt == par:continue
      else:
        var t = dfs(p,nxt)
        if t:
          loopE[p][nIdx]=true
          loopE[nxt][invE[p][nIdx]]=true
        result = result or t


  if es.anyIt(it.len>=3):
    var
      s = dfsFindLoop(-1,0)
      ans = inithashset[int]()
    touch.fill(false)
    discard dfs(-1,s)
    for p in 0..<n:
      for nIdx in 0..<es[p].len:
        if loopE[p][nIdx]:
          ans.incl(ids[p][nIdx])
    echo ans.len
    echo ans.toseq.join(" ")
    
    
    

  else:
    # 全部ループ
    var ans = newseq[int]()
    for i in 1..n:
      ans.add(i)
    echo n
    echo ans.join(" ")
      
     
solve()

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード