結果

問題 No.177 制作進行の宮森あおいです！
ユーザー むらためむらため
提出日時 2019-01-31 09:19:42
言語 Nim
(2.0.2)
結果
AC  
実行時間 57 ms / 2,000 ms
コード長 1,720 bytes
コンパイル時間 2,859 ms
コンパイル使用メモリ 64,628 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 11:14:13
合計ジャッジ時間 3,641 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 16 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 3 ms
6,944 KB
testcase_09 AC 36 ms
6,944 KB
testcase_10 AC 57 ms
6,944 KB
testcase_11 AC 49 ms
6,944 KB
testcase_12 AC 28 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sequtils
template times*(n:int,body) = (for _ in 0..<n: body)


template useMaxFlow =
  # fordFullkerson : 最大流/最小カット O(FE) (F:最大流の流量)
  type Edge = tuple[dst,cap,rev:int]
  type Graph = seq[seq[Edge]]
  proc initFlow(maxSize:int):Graph = newSeqWith(maxSize,newSeq[Edge]())
  proc add(G:var Graph,src,dst,cap:int) =
    G[src] &= (dst,cap,G[dst].len)
    G[dst] &= (src,0,G[src].len - 1)
  proc fordFullkerson(G:var Graph,src,dst:int) : int =
    var used : seq[bool]
    proc dfs(G:var Graph,src,dst,flow:int) : int =
      if src == dst : return flow
      used[src] = true
      for i,e in G[src]:
        if used[e.dst] or e.cap <= 0 : continue
        let d = G.dfs(e.dst,dst,flow.min(e.cap))
        if d <= 0 : continue
        G[src][i].cap -= d
        G[e.dst][e.rev].cap += d
        return d
    while true:
      used = newSeq[bool](G.len)
      const INF = 1e10.int
      let flow = G.dfs(src,dst,INF)
      if flow == 0 : return
      result += flow
useMaxFlow()

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': return
    result = 10 * result + k.ord - '0'.ord

let w = scan()
let n = scan()
let J = newSeqWith(n,scan())
let m = scan()
let C = newSeqWith(m,scan())

var f = initFlow(n+m+2) # J:0..<n | C:n+0..<n+m | n+m -> n+m+1
let src = n + m
let dst = n + m + 1
for i,j in J: f.add(src,i,j)
for i,c in C: f.add(n+i,dst,c)
for c in n..<n+m:
  let q = scan()
  let X = newSeqWith(q,scan()-1)
  let OK = toSeq(0..<n).filterIt(it notin X)
  for j in OK:
    f.add(j,c,1e10.int)
if f.fordFullkerson(src,dst) < w : echo "BANSAKUTSUKITA"
else: echo "SHIROBAKO"
0