#943477 (Nim) No.2604 Initial Motion

提出ソース
結果

問題	No.2604 Initial Motion
ユーザー	kemuniku
提出日時	2024-01-12 22:16:56
言語	Nim (2.2.0)
結果	AC
実行時間	257 ms / 3,000 ms
コード長	12,500 bytes
コンパイル時間	5,501 ms
コンパイル使用メモリ	79,232 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-27 22:45:50
合計ジャッジ時間	10,767 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 39
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
yukicoder

結果

ソースコード
