結果
| 問題 | No.2674 k-Walk on Bipartite |
| ユーザー |
 寝癖
|
| 提出日時 | 2024-03-15 22:45:05 |
| 言語 | Nim (2.0.2) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,973 bytes |
| コンパイル時間 | 3,928 ms |
| コンパイル使用メモリ | 78,272 KB |
| 実行使用メモリ | 810,904 KB |
| 最終ジャッジ日時 | 2024-09-30 02:13:34 |
| 合計ジャッジ時間 | 7,719 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 1 ms
6,820 KB |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 1 ms
6,816 KB |
| testcase_07 | MLE | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
ソースコード
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 = newSeq[int](N)
proc dfs(v: int, c: int, p: int) =
color[v] = c
for u in to[v]:
if u == p: continue
dfs(u, c xor 1, v)
dfs(s, 0, -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, INF)
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] == INF:
dist[u] = dist[v] + 1
q.addLast(u)
if dist[t] <= k and (k - dist[t]) % 2 == 0:
print("Yes")
else:
print("Unknown")