結果
| 問題 | 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 |
ソースコード
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