#943477 (Nim) No.2604 Initial Motion

提出ソース

結果

問題	No.2604 Initial Motion
ユーザー	kemuniku
提出日時	2024-01-12 22:16:56
言語	Nim (2.0.2)
結果	AC
実行時間	251 ms / 3,000 ms
コード長	12,500 bytes
コンパイル時間	4,324 ms
コンパイル使用メモリ	80,704 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-01-12 22:17:06
合計ジャッジ時間	9,079 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	7 ms 6,676 KB
testcase_04	AC	7 ms 6,676 KB
testcase_05	AC	7 ms 6,676 KB
testcase_06	AC	7 ms 6,676 KB
testcase_07	AC	7 ms 6,676 KB
testcase_08	AC	8 ms 6,676 KB
testcase_09	AC	7 ms 6,676 KB
testcase_10	AC	7 ms 6,676 KB
testcase_11	AC	7 ms 6,676 KB
testcase_12	AC	7 ms 6,676 KB
testcase_13	AC	146 ms 6,676 KB
testcase_14	AC	93 ms 6,676 KB
testcase_15	AC	64 ms 6,676 KB
testcase_16	AC	125 ms 6,676 KB
testcase_17	AC	183 ms 6,676 KB
testcase_18	AC	170 ms 6,676 KB
testcase_19	AC	164 ms 6,676 KB
testcase_20	AC	124 ms 6,676 KB
testcase_21	AC	97 ms 6,676 KB
testcase_22	AC	158 ms 6,676 KB
testcase_23	AC	108 ms 6,676 KB
testcase_24	AC	140 ms 6,676 KB
testcase_25	AC	125 ms 6,676 KB
testcase_26	AC	127 ms 6,676 KB
testcase_27	AC	80 ms 6,676 KB
testcase_28	AC	108 ms 6,676 KB
testcase_29	AC	142 ms 6,676 KB
testcase_30	AC	87 ms 6,676 KB
testcase_31	AC	120 ms 6,676 KB
testcase_32	AC	82 ms 6,676 KB
testcase_33	AC	4 ms 6,676 KB
testcase_34	AC	63 ms 6,676 KB
testcase_35	AC	143 ms 6,676 KB
testcase_36	AC	190 ms 6,676 KB
testcase_37	AC	4 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	251 ms 6,676 KB
testcase_41	AC	248 ms 6,676 KB

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

ソースコード

raw source code

import macros
macro Please(x): untyped = nnkStmtList.newTree()

Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL



import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import macros
ImportExpand "cplib/tmpl/sheep.nim" <=== "when not declared CPLIB_TMPL_SHEEP:\n    const CPLIB_TMPL_SHEEP* = 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    #入力系\n    proc scanf(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    proc getchar(): char {.importc: \"getchar_unlocked\", header: \"<stdio.h>\", discardable.}\n    proc ii(): int {.inline.} = scanf(\"%lld\\n\", addr result)\n    proc lii(N: int): seq[int] {.inline.} = newSeqWith(N, ii())\n    proc si(): string {.inline.} =\n        result = \"\"\n        var c: char\n        while true:\n            c = getchar()\n            if c == ' ' or c == '\\n':\n                break\n            result &= c\n    #chmin,chmax\n    template `max=`(x, y) = x = max(x, y)\n    template `min=`(x, y) = x = min(x, y)\n    #bit演算\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: 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: 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 `@`(x: int): seq[int] =\n        for i in 0..<64:\n            if x[i]:\n                result.add(i)\n    #便利な変換\n    proc `!`(x: char, a = '0'): int = int(x)-int(a)\n    #定数\n    const INF = int(3300300300300300491)\n    #converter\n\n    #range\n    iterator range(start: int, ends: int, step: int): int =\n        var i = start\n        if step < 0:\n            while i > ends:\n                yield i\n                i += step\n        elif step > 0:\n            while i < ends:\n                yield i\n                i += step\n    iterator range(ends: int): int = (for i in 0..<ends: yield i)\n    iterator range(start: int, ends: int): int = (for i in\n            start..<ends: yield i)\n    discard\n"

# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/mincostflow.nim
ImportExpand "atcoder/mincostflow.nim" <=== "when not declared ATCODER_MINCOSTFLOW_HPP:\n  const ATCODER_MINCOSTFLOW_HPP* = 1\n\n  import std/heapqueue\n  import std/algorithm\n  #[ import atcoder/internal_csr ]#\n  when not declared ATCODER_INTERNAL_CSR_HPP:\n    const ATCODER_INTERNAL_CSR_HPP* = 1\n  \n    type csr*[E] = object\n      start*: seq[int]\n      elist*: seq[E]\n    proc initCsr*[E](n:int, edges:seq[(int, E)]):csr[E] =\n      var start = newSeq[int](n + 1)\n      var elist = newSeq[E](edges.len)\n      for e in edges: start[e[0] + 1].inc\n      for i in 1..n: start[i] += start[i - 1]\n      var counter = start\n      for e in edges:\n        elist[counter[e[0]]] = e[1]\n        counter[e[0]].inc\n      return csr[E](start:start, elist:elist)\n    discard\n  #[ import atcoder/internal_queue ]#\n  when not declared ATCODER_INTERNAL_QUEUE_HPP:\n    const ATCODER_INTERNAL_QUEUE_HPP* = 1\n  \n    type simple_queue[T] = object\n      payload:seq[T]\n      pos:int\n    proc init_simple_queue*[T]():auto = simple_queue[T](payload:newSeq[T](), pos:0)\n  # TODO\n  #      void reserve(int n) { payload.reserve(n); }\n    proc len*[T](self:simple_queue[T]):int = self.payload.len - self.pos\n    proc empty*[T](self:simple_queue[T]):bool = self.pos == self.payload.len\n    proc push*[T](self:var simple_queue[T], t:T) = self.payload.add(t)\n    proc front*[T](self:simple_queue[T]):T = self.payload[self.pos]\n    proc clear*[T](self:var simple_queue[T]) =\n      self.payload.setLen(0)\n      self.pos = 0;\n    proc pop*[T](self:var simple_queue[T]) = self.pos.inc\n    discard\n  #[ import atcoder/internal_heap ]#\n  when not declared ATCODER_INTERNAL_HEAP:\n    const ATCODER_INTERNAL_HEAP* = 1\n    proc push_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n      var i = p.b\n      while i > 0:\n        var p = (i - 1) shr 1\n        if v[p] < v[i]: swap v[p], v[i]\n        else: break\n        i = p\n    proc pop_heap*[T](v: var openArray[T], p:Slice[int]) {.inline.} =\n      swap v[0], v[p.b]\n      var p = p\n      p.b.dec\n      var i = 0\n      while true:\n        var (c0, c1) = (i * 2 + 1, i * 2 + 2)\n        if c1 in p:\n          if v[c1] > v[i]:\n            if v[c0] > v[c1]:\n              swap(v[i], v[c0])\n              i = c0\n            else:\n              swap(v[i], v[c1])\n              i = c1\n          elif v[c0] > v[i]:\n            swap(v[i], v[c0])\n            i = c0\n          else: break\n        elif c0 in p:\n          if v[c0] > v[i]:\n            swap(v[i], v[c0])\n            i = c0\n          else: break\n        else: break\n    discard\n\n  type MCFEdge*[Cap, Cost] = object\n    src*, dst*: int\n    cap*, flow*: Cap\n    cost*: Cost\n\n  type MCFInternalEdge[Cap, Cost] = object\n    dst, rev: int\n    cap: Cap\n    cost: Cost\n\n  type MCFGraph*[Cap, Cost] = object\n    n:int\n    edges:seq[MCFEdge[Cap, Cost]]\n  \n  proc initMCFGraph*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n  proc initMinCostFLow*[Cap, Cost](n:int):MCFGraph[Cap, Cost] = result.n = n\n\n  proc add_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], src, dst:int, cap:Cap, cost:Cost):int {.discardable.} =\n    assert src in 0..<self.n\n    assert dst in 0..<self.n\n    assert 0 <= cap\n    assert 0 <= cost\n    var m = self.edges.len\n    self.edges.add(MCFEdge[Cap, Cost](src:src, dst:dst, cap:cap, flow:0, cost:cost))\n    return m\n\n  proc get_edge*[Cap, Cost](self:MCFGraph[Cap, Cost], i:int): MCFEdge[Cap, Cost] =\n    let m = self.edges.len\n    assert i in 0..<m\n    return self.edges[i]\n\n  proc edges*[Cap, Cost](self:var MCFGraph[Cap, Cost]):seq[MCFEdge[Cap, Cost]] = self.edges\n  type MCFQ[Cost] = object\n    key:Cost\n    dst:int\n  proc `<`*[Cost](l, r:MCFQ[Cost]):bool = l.key > r.key\n\n  proc slope*[Cap, Cost](self: MCFGraph[Cap, Cost], g:var csr[MCFInternalEdge[Cap, Cost]], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n    ## variants (C = maxcost):\n    ## -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0\n    ## reduced cost (= e.cost + dual[e.src] - dual[e.to]) >= 0 for all edge\n\n    ## dual_dist[i] = (dual[i], dist[i])\n    var\n      dual_dist = newSeq[tuple[dual, dist:Cost]](self.n)\n      prev_e = newSeq[int](self.n)\n      vis = newSeq[bool](self.n)\n      que_min = newSeq[int]()\n      que = newSeq[MCFQ[Cost]]()\n    proc dual_ref(g:csr[MCFInternalEdge[Cap, Cost]]):bool =\n      for i in 0..<self.n: dual_dist[i].dist = Cost.high\n      vis.fill(false)\n      que_min.setLen(0)\n      que.setLen(0)\n\n      # que[0..heap_r) was heapified\n      var heap_r = 0\n\n      dual_dist[s].dist = 0\n      que_min.add(s)\n      while que_min.len > 0 or que.len > 0:\n        var v:int\n        if que_min.len > 0:\n          v = que_min.pop()\n        else:\n          while heap_r < que.len:\n            heap_r.inc\n            que.push_heap(0 ..< heap_r)\n          v = que[0].dst\n          que.pop_heap(0 ..< que.len)\n          discard que.pop()\n          heap_r.dec\n        if vis[v]: continue\n        vis[v] = true\n        if v == t: break\n        ## dist[v] = shortest(s, v) + dual[s] - dual[v]\n        ## dist[v] >= 0 (all reduced cost are positive)\n        ## dist[v] <= (n-1)C\n        let (dual_v, dist_v) = dual_dist[v]\n        for i in g.start[v] ..< g.start[v + 1]:\n          let e = g.elist[i]\n          if e.cap == Cap(0): continue\n          ## |-dual[e.to] + dual[v]| <= (n-1)C\n          ## cost <= C - -(n-1)C + 0 = nC\n          let cost = e.cost - dual_dist[e.dst].dual + dual_v\n          if dual_dist[e.dst].dist - dist_v > cost:\n            let dist_to = dist_v + cost\n            dual_dist[e.dst].dist = dist_to\n            prev_e[e.dst] = e.rev\n            if dist_to == dist_v:\n              que_min.add(e.dst)\n            else:\n              que.add(MCFQ[Cost](key:dist_to, dst:e.dst))\n      if not vis[t]:\n        return false\n\n      for v in 0..<self.n:\n        if not vis[v]: continue\n        # dual[v] = dual[v] - dist[t] + dist[v]\n        #     = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +\n        #     (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,\n        #     t) + dual[t] + shortest(s, v) = shortest(s, v) -\n        #     shortest(s, t) >= 0 - (n-1)C\n        dual_dist[v].dual -= dual_dist[t].dist - dual_dist[v].dist\n      return true\n    var\n      flow:Cap = 0\n      cost:Cost = 0\n      prev_cost_per_flow:Cost = -1\n    result = @[(Cap(0), Cost(0))]\n    while flow < flow_limit:\n      if not g.dual_ref(): break\n      var c = flow_limit - flow\n      block:\n        var v = t\n        while v != s:\n          c = min(c, g.elist[g.elist[prev_e[v]].rev].cap)\n          v = g.elist[prev_e[v]].dst\n      block:\n        var v = t\n        while v != s:\n          var e = g.elist[prev_e[v]].addr\n          e[].cap += c\n          g.elist[e[].rev].cap -= c\n          v = g.elist[prev_e[v]].dst\n      let d = -dual_dist[s].dual\n      flow += c\n      cost += c * d\n      if prev_cost_per_flow == d:\n        discard result.pop()\n      result.add((flow, cost))\n      prev_cost_per_flow = d\n\n  proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):seq[tuple[cap:Cap, cost:Cost]] =\n    assert s in 0..<self.n\n    assert t in 0..<self.n\n    assert s != t\n\n    let m = self.edges.len\n    var edge_idx = newSeq[int](m)\n\n    var g = block:\n      var degree = newSeq[int](self.n)\n      var redge_idx = newSeq[int](m)\n      var elist = newSeqOfCap[(int, MCFInternalEdge[Cap, Cost])](2 * m)\n      for i in 0..<m:\n        let e = self.edges[i]\n        edge_idx[i] = degree[e.src]\n        degree[e.src].inc\n        redge_idx[i] = degree[e.dst]\n        degree[e.dst].inc\n        elist.add((e.src, MCFInternalEdge[Cap, Cost](dst: e.dst, rev: -1, cap:e.cap - e.flow, cost:e.cost)))\n        elist.add((e.dst, MCFInternalEdge[Cap, Cost](dst: e.src, rev: -1, cap:e.flow, cost: -e.cost)))\n      var g = initCSR[MCFInternalEdge[Cap, Cost]](self.n, elist)\n      for i in 0..<m:\n        let e = self.edges[i]\n        edge_idx[i] += g.start[e.src]\n        redge_idx[i] += g.start[e.dst]\n        g.elist[edge_idx[i]].rev = redge_idx[i];\n        g.elist[redge_idx[i]].rev = edge_idx[i];\n      g\n\n    result = self.slope(g, s, t, flow_limit)\n\n    for i in 0..<m:\n      let e = g.elist[edge_idx[i]]\n      self.edges[i].flow = self.edges[i].cap - e.cap\n  proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int, flow_limit:Cap):tuple[cap:Cap, cost:Cost] = self.slope(s, t, flow_limit)[^1]\n  proc flow*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):tuple[cap:Cap, cost:Cost] = self.flow(s, t, Cap.high)\n  proc slope*[Cap, Cost](self:var MCFGraph[Cap, Cost], s, t:int):seq[tuple[cap:Cap, cost:Cost]] = self.slope(s, t, Cap.high)\n\n  #### chaemon added\n  proc reset*[Cap, Cost](self: var MCFGraph[Cap, Cost]) =\n    for e in self.edges.mitems:\n      e.flow = 0\n\n  proc set_edge*[Cap, Cost](self: var MCFGraph[Cap, Cost], i:int, cap:Cap, cost:Cost) =\n    assert 0 <= cap\n    assert 0 <= cost\n    var m = self.edges.len\n    assert i in 0 ..< m\n    edges[i].cap = cap\n    edges[i].cost = cost\n  discard\n"

var K,N,M = ii()
var G = init_mcf_graph[int,int](N+N+2)
var A = newSeqWith(K,ii()-1).toCountTable()
var B = newSeqWith(N,ii())
for i,v in A:
    G.add_edge(N,i,v,0)
for i in range(N):
    if B[i] != 0:
        G.add_edge(i,N+1,B[i],0)

for i in range(M):
    var U,V,D = ii()
    U-=1;V-=1
    G.add_edge(U,V,INF,D)
    G.add_edge(V,U,INF,D)

echo G.slope(N,N+1)[^1].cost

yukicoder

結果

テストケース

ソースコード