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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	dot_haraai
提出日時	2021-06-05 20:51:37
言語	Nim (2.0.2)
結果	AC
実行時間	179 ms / 2,000 ms
コード長	2,120 bytes
コンパイル時間	4,517 ms
コンパイル使用メモリ	88,960 KB
実行使用メモリ	25,984 KB
最終ジャッジ日時	2024-11-21 19:43:46
合計ジャッジ時間	16,717 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	1 ms 5,248 KB
testcase_18	AC	1 ms 5,248 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	1 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	1 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	1 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	1 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	2 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	3 ms 5,248 KB
testcase_44	AC	2 ms 5,248 KB
testcase_45	AC	2 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	2 ms 5,248 KB
testcase_48	AC	2 ms 5,248 KB
testcase_49	AC	1 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	3 ms 5,248 KB
testcase_52	AC	3 ms 5,248 KB
testcase_53	AC	3 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	2 ms 5,248 KB
testcase_56	AC	1 ms 5,248 KB
testcase_57	AC	2 ms 5,248 KB
testcase_58	AC	2 ms 5,248 KB
testcase_59	AC	1 ms 5,248 KB
testcase_60	AC	2 ms 5,248 KB
testcase_61	AC	2 ms 5,248 KB
testcase_62	AC	1 ms 5,248 KB
testcase_63	AC	11 ms 5,248 KB
testcase_64	AC	4 ms 5,248 KB
testcase_65	AC	8 ms 5,248 KB
testcase_66	AC	7 ms 5,248 KB
testcase_67	AC	4 ms 5,248 KB
testcase_68	AC	7 ms 5,248 KB
testcase_69	AC	9 ms 5,248 KB
testcase_70	AC	5 ms 5,248 KB
testcase_71	AC	4 ms 5,248 KB
testcase_72	AC	9 ms 5,248 KB
testcase_73	AC	4 ms 5,248 KB
testcase_74	AC	9 ms 5,248 KB
testcase_75	AC	7 ms 5,248 KB
testcase_76	AC	3 ms 5,248 KB
testcase_77	AC	6 ms 5,248 KB
testcase_78	AC	10 ms 5,248 KB
testcase_79	AC	10 ms 5,248 KB
testcase_80	AC	9 ms 5,248 KB
testcase_81	AC	11 ms 5,248 KB
testcase_82	AC	10 ms 5,248 KB
testcase_83	AC	147 ms 18,936 KB
testcase_84	AC	157 ms 18,688 KB
testcase_85	AC	75 ms 12,800 KB
testcase_86	AC	121 ms 16,512 KB
testcase_87	AC	153 ms 17,664 KB
testcase_88	AC	18 ms 5,376 KB
testcase_89	AC	156 ms 18,816 KB
testcase_90	AC	81 ms 13,312 KB
testcase_91	AC	62 ms 11,136 KB
testcase_92	AC	32 ms 7,296 KB
testcase_93	AC	107 ms 15,744 KB
testcase_94	AC	104 ms 14,592 KB
testcase_95	AC	101 ms 14,464 KB
testcase_96	AC	130 ms 18,048 KB
testcase_97	AC	50 ms 9,984 KB
testcase_98	AC	142 ms 18,176 KB
testcase_99	AC	70 ms 12,416 KB
testcase_100	AC	138 ms 19,328 KB
testcase_101	AC	26 ms 6,912 KB
testcase_102	AC	14 ms 5,248 KB
testcase_103	AC	29 ms 7,296 KB
testcase_104	AC	43 ms 8,832 KB
testcase_105	AC	112 ms 15,744 KB
testcase_106	AC	57 ms 10,496 KB
testcase_107	AC	163 ms 18,816 KB
testcase_108	AC	157 ms 18,688 KB
testcase_109	AC	114 ms 15,616 KB
testcase_110	AC	88 ms 14,464 KB
testcase_111	AC	108 ms 15,232 KB
testcase_112	AC	38 ms 8,576 KB
testcase_113	AC	88 ms 14,080 KB
testcase_114	AC	54 ms 10,368 KB
testcase_115	AC	18 ms 5,504 KB
testcase_116	AC	62 ms 11,520 KB
testcase_117	AC	38 ms 8,704 KB
testcase_118	AC	134 ms 17,792 KB
testcase_119	AC	68 ms 12,288 KB
testcase_120	AC	123 ms 17,280 KB
testcase_121	AC	35 ms 7,808 KB
testcase_122	AC	62 ms 11,392 KB
testcase_123	AC	1 ms 5,248 KB
testcase_124	AC	179 ms 25,984 KB
testcase_125	AC	162 ms 25,984 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

結果

テストケース

コンパイルメッセージ

ソースコード