結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | terasa |
提出日時 | 2022-12-17 11:09:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 2,543 bytes |
コンパイル時間 | 1,711 ms |
コンパイル使用メモリ | 86,860 KB |
実行使用メモリ | 82,876 KB |
最終ジャッジ日時 | 2023-08-10 13:27:22 |
合計ジャッジ時間 | 5,228 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 156 ms
80,176 KB |
testcase_01 | AC | 156 ms
80,148 KB |
testcase_02 | AC | 157 ms
80,276 KB |
testcase_03 | AC | 169 ms
81,268 KB |
testcase_04 | AC | 161 ms
80,680 KB |
testcase_05 | AC | 177 ms
81,724 KB |
testcase_06 | AC | 179 ms
82,296 KB |
testcase_07 | AC | 160 ms
80,564 KB |
testcase_08 | AC | 173 ms
81,752 KB |
testcase_09 | AC | 184 ms
82,876 KB |
testcase_10 | AC | 187 ms
82,620 KB |
testcase_11 | AC | 182 ms
82,512 KB |
testcase_12 | AC | 180 ms
82,700 KB |
testcase_13 | AC | 157 ms
79,908 KB |
testcase_14 | AC | 154 ms
80,136 KB |
testcase_15 | AC | 157 ms
80,280 KB |
ソースコード
from typing import List, Tuple, Callable, TypeVar, Optional import sys import itertools import heapq import bisect import math from collections import deque, defaultdict from functools import lru_cache, cmp_to_key input = sys.stdin.readline if __file__ != 'prog.py': sys.setrecursionlimit(10 ** 6) def readints(): return map(int, input().split()) def readlist(): return list(readints()) def readstr(): return input()[:-1] class Dinic: def __init__(self, N, inf=1 << 50): self.N = N self.G = [[] for _ in range(self.N)] self.inf = inf def add_edge(self, u, v, cap): forward = [cap, v, None] backward = [0, u, None] forward[2] = backward backward[2] = forward self.G[u].append(forward) self.G[v].append(backward) def flow(self, s, t): flow = 0 while True: self._bfs(s, t) if self.level[t] is None: return flow *self.iter, = map(iter, self.G) f = self.inf while f > 0: f = self._dfs(s, t, self.inf) flow += f def _bfs(self, s, t): self.level = [None] * self.N dq = deque([s]) self.level[s] = 0 while dq: v = dq.popleft() for cap, d, _ in self.G[v]: if cap == 0: continue if self.level[d] is None: self.level[d] = self.level[v] + 1 dq.append(d) def _dfs(self, u, t, f): if u == t: return f for e in self.iter[u]: cap, v, rev = e if cap == 0: continue if self.level[v] > self.level[u]: delta = self._dfs(v, t, min(f, cap)) if delta > 0: e[0] -= delta rev[0] += delta return delta return 0 W = int(input()) N = int(input()) J = readlist() M = int(input()) C = readlist() comb = [[True for _ in range(M)] for _ in range(N)] for j in range(M): q, *X = readints() for i in X: i -= 1 comb[i][j] = False solver = Dinic(N + M + 2) INF = 1 << 50 for i in range(N): solver.add_edge(0, i + 1, J[i]) for j in range(M): solver.add_edge(N + 1 + j, N + 1 + M, C[j]) for i in range(N): for j in range(M): if comb[i][j]: solver.add_edge(i + 1, N + 1 + j, INF) flow = solver.flow(0, N + M + 1) print('SHIROBAKO' if flow >= W else 'BANSAKUTSUKITA')