#631416 (PyPy3) No.177 制作進行の宮森あおいです！

• 問題: No.177 制作進行の宮森あおいです！
• ユーザー: tktk_snsn
• 提出日時: 2021-03-19 19:47:30
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 69 ms / 2,000 ms
• コード長: 3,895 bytes
• コンパイル時間: 320 ms
• コンパイル使用メモリ: 82,600 KB
• 実行使用メモリ: 74,472 KB
• 最終ジャッジ日時: 2024-11-18 16:37:25
• 合計ジャッジ時間: 1,697 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 13

ソースコード

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from collections import deque
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10**9
class MF_graph(object):
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]  # to, rev, cap
        self.pos = []
    def add_edge(self, frm, to, cap):
        """ frmからtoへ容量cap, 流量0の辺を追加, 何番目の辺かを返す"""
        m = len(self.pos)
        self.pos.append((frm, len(self.g[frm])))
        self.g[frm].append([to, len(self.g[to]), cap])
        self.g[to].append([frm, len(self.g[frm]) - 1, 0])
        return m
    def __get_edge(self, i):
        e_to, e_rev, e_cap = self.g[self.pos[i][0]][self.pos[i][1]]
        re_to, _, re_cap = self.g[e_to][e_rev]
        # from, to, cap, flow
        return (re_to, e_to, e_cap + re_cap, re_cap)
    def edges(self):
        """ 辺の情報を返す(frm, to, cap, flow) """
        m = len(self.pos)
        for i in range(m):
            yield self.__get_edge(i)
    def change_edge(self, i, new_cap, new_flow):
        """ i番目に追加された辺の容量,流量をnew_cap, new_flowに変更する """
        f, s = self.pos[i]
        rf, rs, _ = self.g[f][s]
        self.g[f][s][2] = new_cap - new_flow
        self.g[rf][rs][2] = new_flow
        return
    def __dfs(self, s, v, up):
        if v == s:
            return up
        res = 0
        level_v = self.level[v]
        for i in range(self.iter[v], len(self.g[v])):
            u_to, u_rev, _ = self.g[v][i]
            if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0:
                continue
            d = self.__dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2]))
            if d <= 0:
                continue
            self.g[v][i][2] += d
            self.g[u_to][u_rev][2] -= d
            res += d
            if res == up:
                break
        return res
    def flow(self, s, t, flow_limit=10**18):
        """ sからtへflow_limitだけ流す。流せた量を返す """
        self.iter = [0] * self.n
        flow = 0
        while flow < flow_limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            que = deque([s])
            while que:
                v = que.popleft()
                for u_to, _, u_cap in self.g[v]:
                    if u_cap == 0 or self.level[u_to] >= 0:
                        continue
                    self.level[u_to] = self.level[v] + 1
                    if u_to == t:
                        break
                    que.append(u_to)
            if self.level[t] == -1:
                break
            self.iter = [0] * self.n
            while flow < flow_limit:
                f = self.__dfs(s, t, flow_limit - flow)
                if not f:
                    break
                flow += f
        return flow
    def min_cut(self, s):
        """ 最小カットを返す。sから到達可能だとTrue """
        visited = [False] * self.n
        que = deque([s])
        while que:
            v = que.popleft()
            visited[v] = True
            for u_to, _, u_cap in self.g[v]:
                if u_cap and (not visited[u_to]):
                    visited[u_to] = True
                    que.append(u_to)
        return visited
W = int(input())
N = int(input())
J = tuple(map(int, input().split()))
M = int(input())
C = tuple(map(int, input().split()))
cap = [[inf] * N for _ in range(M)]
for m in range(M):
    _, *X = map(int, input().split())
    for n in X:
        cap[m][n-1] = 0
G = MF_graph(N + M + 2)
source = N + M
sink = source + 1
for i, j in enumerate(J):
    G.add_edge(source, i, j)
for i, c in enumerate(C):
    G.add_edge(i + N, sink, c)
for n in range(N):
    for m in range(M):
        G.add_edge(n, N+m, cap[m][n])
flow = G.flow(source, sink)
if flow >= W:
    print("SHIROBAKO")
else:
    print("BANSAKUTSUKITA")
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX