#960831 (Nim) No.2674 k-Walk on Bipartite

提出ソース

結果

問題	No.2674 k-Walk on Bipartite
ユーザー	寝癖
提出日時	2024-03-15 23:05:23
言語	Nim (2.0.2)
結果	WA
実行時間	-
コード長	7,064 bytes
コンパイル時間	3,757 ms
コンパイル使用メモリ	77,940 KB
実行使用メモリ	21,120 KB
最終ジャッジ日時	2024-09-30 02:39:45
合計ジャッジ時間	5,996 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	1 ms 6,820 KB
testcase_07	AC	43 ms 10,872 KB
testcase_08	AC	86 ms 17,152 KB
testcase_09	WA	-
testcase_10	AC	103 ms 19,968 KB
testcase_11	WA	-
testcase_12	AC	104 ms 21,120 KB
testcase_13	WA	-
testcase_14	AC	12 ms 7,936 KB
testcase_15	AC	93 ms 20,884 KB
testcase_16	AC	64 ms 13,648 KB
testcase_17	AC	68 ms 16,384 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	37 ms 11,264 KB
testcase_21	AC	68 ms 16,768 KB
testcase_22	WA	-
testcase_23	AC	2 ms 6,816 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 6,820 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	2 ms 6,820 KB
testcase_33	AC	1 ms 6,820 KB
testcase_34	AC	2 ms 6,816 KB
testcase_35	AC	1 ms 6,820 KB
testcase_36	AC	1 ms 6,820 KB
testcase_37	AC	1 ms 6,816 KB
testcase_38	AC	1 ms 6,820 KB

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

ソースコード

raw source code

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
ImportExpand "neguse/tmpl.nim" <=== "when not declared NEGUSE_TMPL:\n  const NEGUSE_TMPL* = 1\n  {.warning[UnusedImport]: off.}\n  {.hint[XDeclaredButNotUsed]: off.}\n  import algorithm\n  import sequtils\n  import tables\n  import macros\n  import math\n  import sets\n  import strutils\n  import strformat\n  import sugar\n  import heapqueue\n  import streams\n  import deques\n  import bitops\n  import std/lenientops\n  import options\n  # ACL\n  #[ import atcoder/header ]#\n  when not declared ATCODER_HEADER_HPP:\n    const ATCODER_HEADER_HPP* = 1\n    {.hints:off checks:off assertions:on optimization:speed.}\n    {. warning[UnusedImport]:off .}\n    import std/algorithm as algorithm_lib\n    import std/sequtils as sequils_lib\n    import std/tables as tables_lib\n    import std/macros as macros_lib\n    import std/math as math_lib\n    import std/sets as sets_lib\n    import std/strutils as strutils_lib\n    import std/streams as streams_lib\n    import std/strformat as strformat_lib\n  \n    proc scanf*(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar*(): char {.header: \"<stdio.h>\", varargs.}\n    proc nextInt*(base:int = 0): int =\n      scanf(\"%lld\",addr result)\n      result -= base\n    proc nextFloat*(): float = scanf(\"%lf\",addr result)\n    proc nextString*(): string =\n      var get = false;result = \"\"\n      while true:\n        var c = getchar()\n        if int(c) > int(' '): get = true;result.add(c)\n        elif get: break\n    template `max=`*(x,y:typed):void = x = max(x,y)\n    template `min=`*(x,y:typed):void = x = min(x,y)\n    template inf*(T): untyped = \n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else: assert(false)\n  \n    discard\n  #[ import atcoder/extra/other/inf ]#\n  when not declared ATCODER_INF_HPP:\n    const ATCODER_INF_HPP* = 1\n    import sequtils\n    template inf*(T: typedesc): untyped =\n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else:\n        static: assert(false)\n    template infRepr*[T](x: T): string =\n      when T is seq or T is array:\n        \"@[\" & x.mapIt(it.infRepr).join(\", \") & \"]\"\n      elif x is SomeInteger or x is SomeFloat:\n        when x is SomeUnsignedInt:\n          if x >= T.inf: \"inf\"\n          else: $x\n        else:\n          if x >= T.inf: \"inf\"\n          elif x <= -T.inf: \"-inf\"\n          else: $x\n      else:\n        $x\n    proc isInf*[T](x: T): bool = x >= T.inf\n    proc `∞`*(T: typedesc): T = T.inf\n    proc `*!`*[T: SomeInteger](a, b: T): T =\n      if a == T(0) or b == T(0): return T(0)\n      var sgn = T(1)\n      if a < T(0): sgn = -sgn\n      if b < T(0): sgn = -sgn\n      let a = abs(a)\n      let b = abs(b)\n      if b > T.inf div a: result = T.inf\n      else: result = min(T.inf, a * b)\n      result *= sgn\n    proc `+!`*[T: SomeInteger](a, b: T): T =\n      result = a + b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    proc `-!`*[T: SomeInteger](a, b: T): T =\n      result = a - b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    discard\n\n  # const INF = int.inf\n  const mod998 = 998244353\n  const mod107 = 1000000007\n  const mod109 = 1000000009\n\n  # 演算子\n  proc `%`(x: int, y: int): int = (((x mod y)+y) mod y)\n  proc `//`(x: int, y: int): int = (((x) - (x%y)) div (y))\n  proc `%=`(x: var int, y: int): void = x = x%y\n  proc `//=`(x: var int, y: int): void = x = x//y\n  proc `**`(x: int, y: int): int = x^y\n  proc `**=`(x: var int, y: int): void = x = x^y\n  proc `^`(x: int, y: int): int = x xor y\n  proc `|`(x: int, y: int): int = x or y\n  proc `&`(x: int, y: int): int = x and y\n  proc `>>`(x: int, y: int): int = x shr y\n  proc `<<`(x: int, y: int): int = x shl y\n  proc `~`(x: int): int = not x\n  proc `^=`(x: var int, y: int): void = x = x ^ y\n  proc `&=`(x: var int, y: int): void = x = x & y\n  proc `|=`(x: var int, y: int): void = x = x | y\n  proc `>>=`(x: var int, y: int): void = x = x >> y\n  proc `<<=`(x: var int, y: int): void = x = x << y\n  proc `[]`(x: int, n: int): bool = (x and (1 shl n)) != 0\n  proc mul128(a, b, m: int): int {.importcpp: \"(__int128)(#) * (#) % (#)\", nodecl.}\n  proc powmod(a, n, m: int): int =\n    result = 1\n    var\n      a = a\n      n = n\n    while n > 0:\n      if n mod 2 != 0: result = mul128(result, a, m)\n      if n > 1: a = mul128(a, a, m)\n      n = n shr 1\n    return result\n  # 入出力\n  proc print(args: varargs[string, infRepr]) = echo args.join(\" \")\n  let readNext = iterator(getsChar: bool = false): string {.closure.} =\n    while true:\n      var si: string\n      try: si = stdin.readLine\n      except EOFError: yield \"\"\n      for s in si.split:\n        if getsChar:\n          for i in 0..<s.len():\n              yield s[i..i]\n        else:\n          if s.isEmptyOrWhitespace: continue\n          yield s\n  proc chmin[T](a: var T, b: T): bool {.discardable.} =\n    if a > b:\n      a = b\n      result = true\n    else:\n      result = false\n  proc chmax[T](a: var T, b: T): bool {.discardable.} =\n    if a < b:\n      a = b\n      result = true\n    else:\n      result = false\n  iterator range(stop: int): int =\n    for i in 0..<stop: yield i\n  iterator range(start: int, stop: int, step: int = 1): int =\n    var i = start\n    if step > 0:\n      while i < stop:\n        yield i\n        i += step\n    elif step < 0:\n      while i > stop:\n        yield i\n        i += step\n    else:\n      discard\n  iterator permutation[T](a: openArray[T], r: int): seq[T] =\n    let n = a.len\n    var p = toSeq(0..<r) & newSeqWith(n-r, INF)\n    var loc = toSeq(0..<r)\n    yield loc.mapIt(a[it])\n    while nextPermutation(p):\n      for i, v in p:\n        if v != INF:\n          loc[v] = i\n      yield loc.mapIt(a[it])\n  iterator combinations[T](a: openArray[T], r: int): seq[T] =\n    let n = a.len\n    var p = newSeqWith(r, false) & newSeqWith(n-r, true)\n    let indices = toSeq(0..<n)\n    yield indices.filterIt(not p[it]).mapIt(a[it])\n    while nextPermutation(p):\n      yield indices.filterIt(not p[it]).mapIt(a[it])\n  discard\n"

var N, M = nextInt()
var s, t, k = nextInt(1)
k += 1
var to = newSeqWith(N, newSeq[int]())
for _ in range(M):
  var a, b = nextInt(1)
  to[a].add(b)
  to[b].add(a)

var color = newSeqWith(N, -1)
proc dfs(v: int, c: int, p: int) =
  color[v] = c
  for u in to[v]:
    if u == p: continue
    if color[u] == -1:
      dfs(u, 1 - c, v)

dfs(s, 0, -1)
if color[t] != -1:
  if (color[s] == color[t] and k % 2 == 1) or (color[s] != color[t] and k % 2 == 0):
    print("No")
    quit()

  var dist = newSeqWith(N, -1)
  var q = initDeque[int]()
  q.addLast(s)
  dist[s] = 0
  while q.len > 0:
    var v = q.popFirst
    for u in to[v]:
      if dist[u] == -1:
        dist[u] = dist[v] + 1
        q.addLast(u)

  if dist[t] != -1 and dist[t] <= k:
    print("Yes")
  else:
    print("Unknown")
else:
  print("Yes")

yukicoder

結果

テストケース

ソースコード