#746430 (PyPy3) No.1984 [Cherry 4th Tune *] Dilemma

提出ソース

結果

問題	No.1984 [Cherry 4th Tune *] Dilemma
ユーザー	👑 Kazun
提出日時	2022-03-17 16:15:56
言語	PyPy3 (7.3.15)
結果	AC
実行時間	168 ms / 2,000 ms
コード長	13,373 bytes
コンパイル時間	1,367 ms
コンパイル使用メモリ	86,920 KB
実行使用メモリ	80,100 KB
最終ジャッジ日時	2023-08-08 08:12:27
合計ジャッジ時間	20,428 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	99 ms 72,152 KB
testcase_01	AC	98 ms 71,756 KB
testcase_02	AC	99 ms 72,136 KB
testcase_03	AC	101 ms 72,060 KB
testcase_04	AC	100 ms 71,804 KB
testcase_05	AC	100 ms 72,132 KB
testcase_06	AC	99 ms 71,916 KB
testcase_07	AC	101 ms 72,188 KB
testcase_08	AC	102 ms 72,296 KB
testcase_09	AC	102 ms 72,172 KB
testcase_10	AC	99 ms 72,152 KB
testcase_11	AC	101 ms 72,252 KB
testcase_12	AC	102 ms 72,008 KB
testcase_13	AC	116 ms 76,264 KB
testcase_14	AC	158 ms 78,980 KB
testcase_15	AC	119 ms 76,928 KB
testcase_16	AC	147 ms 78,636 KB
testcase_17	AC	134 ms 77,504 KB
testcase_18	AC	135 ms 77,400 KB
testcase_19	AC	118 ms 76,980 KB
testcase_20	AC	101 ms 72,284 KB
testcase_21	AC	116 ms 77,112 KB
testcase_22	AC	146 ms 78,336 KB
testcase_23	AC	165 ms 79,360 KB
testcase_24	AC	168 ms 79,448 KB
testcase_25	AC	163 ms 79,484 KB
testcase_26	AC	163 ms 79,204 KB
testcase_27	AC	161 ms 79,544 KB
testcase_28	AC	166 ms 79,464 KB
testcase_29	AC	149 ms 79,032 KB
testcase_30	AC	168 ms 79,828 KB
testcase_31	AC	154 ms 78,980 KB
testcase_32	AC	167 ms 79,444 KB
testcase_33	AC	110 ms 76,304 KB
testcase_34	AC	113 ms 76,284 KB
testcase_35	AC	110 ms 76,300 KB
testcase_36	AC	113 ms 76,204 KB
testcase_37	AC	116 ms 76,828 KB
testcase_38	AC	112 ms 76,404 KB
testcase_39	AC	113 ms 76,624 KB
testcase_40	AC	110 ms 76,240 KB
testcase_41	AC	112 ms 76,464 KB
testcase_42	AC	113 ms 76,316 KB
testcase_43	AC	121 ms 77,308 KB
testcase_44	AC	115 ms 76,120 KB
testcase_45	AC	121 ms 76,952 KB
testcase_46	AC	118 ms 76,784 KB
testcase_47	AC	121 ms 76,920 KB
testcase_48	AC	115 ms 76,788 KB
testcase_49	AC	121 ms 76,984 KB
testcase_50	AC	116 ms 76,280 KB
testcase_51	AC	117 ms 76,972 KB
testcase_52	AC	114 ms 76,524 KB
testcase_53	AC	116 ms 76,784 KB
testcase_54	AC	120 ms 76,832 KB
testcase_55	AC	124 ms 76,616 KB
testcase_56	AC	124 ms 77,012 KB
testcase_57	AC	122 ms 76,936 KB
testcase_58	AC	117 ms 76,748 KB
testcase_59	AC	124 ms 76,956 KB
testcase_60	AC	119 ms 76,676 KB
testcase_61	AC	118 ms 76,760 KB
testcase_62	AC	125 ms 77,044 KB
testcase_63	AC	165 ms 80,100 KB
testcase_64	AC	130 ms 77,896 KB
testcase_65	AC	153 ms 78,952 KB
testcase_66	AC	105 ms 72,248 KB
testcase_67	AC	111 ms 76,036 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#Thansk for aaaaaaaaaa2230
#URL: https://atcoder.jp/contests/practice2/submissions/17017372

from collections import deque
class MaxFlow:
    inf = float("inf")

    class Arc:
        def __init__(self, to, cap, base, direction):
            self.to = to
            self.cap = cap
            self.base = base
            self.rev = None
            self.direction=direction

        def __repr__(self):
            if self.direction==1:
                return "[Source] (To: {}) {} / {}".format(self.to, self.cap,self.base)
            else:
                return "[Target] (From: {}) {} / {}".format(self.to, self.cap,self.base)

    def __init__(self, N):
        """ N 頂点のフロー場を生成する.
        """

        self.N=N
        self.arc = [[] for _ in range(N)]

    def add_arc(self, v, w, cap):
        """ 容量 cap の有向辺 v → w を加える.
        """

        a= self.Arc(w,cap,cap,1)
        a2 = self.Arc(v,0,cap,-1)
        a.rev = a2
        a2.rev = a
        self.arc[v].append(a)
        self.arc[w].append(a2)

    def add_edge(self, v, w, cap):
        """ 容量 cap の無向辺 v → w を加える."""
        self.add_arc(v,w,cap)
        self.add_arc(w,v,cap)

    def __bfs(self, s, t):
        level = self.level = [self.N]*self.N
        q = deque([s])
        level[s] = 0
        while q:
            now = q.popleft()
            lw = level[now]+1
            for a in self.arc[now]:
                if a.cap and level[a.to]> lw:
                    level[a.to] = lw
                    if a.to == t:
                        return True
                    q.append(a.to)
        return False

    def __dfs(self, s, t, up):
        arc = self.arc
        it = self.it
        level = self.level

        st = deque([t])
        while st:
            v = st[-1]
            if v == s:
                st.pop()
                flow = up
                for w in st:
                    a = arc[w][it[w]].rev
                    flow = min(flow, a.cap)
                for w in st:
                    a = arc[w][it[w]]
                    a.cap += flow
                    a.rev.cap -= flow
                return flow
            lv = level[v]-1
            while it[v] < len(arc[v]):
                a = arc[v][it[v]]
                ra = a.rev
                if ra.cap == 0 or lv != level[a.to]:
                    it[v] += 1
                    continue
                st.append(a.to)
                break
            if it[v] == len(arc[v]):
                st.pop()
                level[v] = self.N
        return 0

    def max_flow(self, source, target, flow_limit=inf):
        """ source から target に高々 flow_limit の水流を流すとき, "新たに流れる" 水流の大きさ"""

        flow = 0
        while flow < flow_limit and self.__bfs(source, target):
            self.it = [0]*self.N
            while flow < flow_limit:
                f = self.__dfs(source, target, flow_limit-flow)
                if f == 0:
                    break
                flow += f
        return flow

    def flow(self):
        """ 現在の フロー場に流れている各辺の流量を求める.

        """

        F=[{} for _ in range(self.N)]
        arc=self.arc
        for v in range(self.N):
            for a in arc[v]:
                if a.direction==1:
                    F[v][a.to]=a.base-a.cap
        return F

    def min_cut(self,s):
        """ s を 0 に含める最小カットを求める.
        """

        group = [1]*self.N
        Q = deque([s])
        while Q:
            v = Q.pop()
            group[v] = 0
            for a in self.arc[v]:
                if a.cap and group[a.to]:
                    Q.append(a.to)
        return group

inf=float("inf")
class Project_Selection_Problem:
    def __init__(self,N):
        """ N 要素の Project Selection Problem を生成する.

        N:int
        """

        self.N=N
        self.ver_num=N+2
        self.source=N
        self.base=0
        self.target=N+1
        self.indivi=[[0,0] for _ in range(N+2)]
        self.mutual=[]

    def set_zero_one(self,x,y,a):
        """ h(x)=0,  h(y)=1 のとき, a (<=0) 点を得るという条件を追加する.

        0<=x,y<N
        a<=0
        """

        assert 0<=x<self.N
        assert 0<=y<self.N
        assert a<=0

        self.mutual.append((x,y,-a))

    def set_zero(self,x,a):
        """ h(x)=0 のとき, a 点を得るという条件を追加する.

        0<=x<N
        """

        assert 0<=x<self.N
        self.indivi[x][0]+=a

    def set_one(self,x,a):
        """ h(x)=1 のとき, a 点を得るという条件を追加する.

        0<=x<N
        """

        assert 0<=x<self.N
        self.indivi[x][1]+=a

    def set_all_zero(self,X,a):
        """ h(x)=0 (forall x in X) のとき, a (>=0) 点を得るという条件を追加する.

        0<=x<N
        a>=0
        """

        assert a>=0

        self.indivi.append([None,None])
        self.ver_num+=1
        self.base+=a

        self.indivi[-1][0]=-a
        for x in X:
            assert 0<=x<self.N
            self.mutual.append((self.ver_num-1,x,inf))


    def set_all_one(self,X,a):
        """ h(x)=1 (forall x in X) のとき, a (>=0) 点を得るという条件を追加する.

        0<=x<N
        a>=0
        """

        assert a>=0

        self.indivi.append([None,None])
        self.ver_num+=1
        self.base+=a

        self.indivi[-1][1]=-a
        for x in X:
            assert 0<=x<self.N
            self.mutual.append((x,self.ver_num-1,inf))

    def set_not_equal(self,x,y,a):
        """ h(x)!=h(y) ならば, a (<=0) 点を得るという条件を追加する.

        0<=x,y<N
        a<=0
        """

        assert 0<=x<self.N and 0<=y<self.N
        assert a<=0

        self.set_zero_one(x,y,a)
        self.set_zero_one(y,x,a)

    def set_equal(self,x,y,a):
        """ h(x)=h(y) ならば, a (>=0) 点を得るという条件を追加する.

        0<=x,y<N
        a>=0
        """

        assert 0<=x<self.N and 0<=y<self.N
        assert a>=0

        self.set_all_zero([x,y],a)
        self.set_all_one([x,y],a)

    def ban_zero(self,x):
        """ h(x)=0 となることを禁止する. (実行したら -inf 点になる)

        0<=x<N
        """

        assert 0<=x<self.N
        self.set_zero(x,-inf)

    def ban_one(self,x):
        """ h(x)=1 となることを禁止する. (実行したら -inf 点になる)

        0<=x<N
        """

        assert 0<=x<self.N
        self.set_one(x,-inf)

    def solve(self,Mode=0):
        """ Project Selection Problem を解く.

        Mode
        0: 最大値のみ
        1: 最大値とそれを達成する例
        """

        F=MaxFlow(self.ver_num)
        base=self.base
        for i in range(self.N):
            F.add_arc(self.source,i,0)
            F.add_arc(i,self.target,0)

            if self.indivi[i][0]>=0:
                base+=self.indivi[i][0]
                F.add_arc(self.source,i,self.indivi[i][0])
            else:
                F.add_arc(i,self.target,-self.indivi[i][0])

            if self.indivi[i][1]>=0:
                base+=self.indivi[i][1]
                F.add_arc(i,self.target,self.indivi[i][1])
            else:
                F.add_arc(self.source,i,-self.indivi[i][1])

        for i in range(self.target+1,self.ver_num):
            if self.indivi[i][0]!=None:
                F.add_arc(self.source,i,-self.indivi[i][0])
            if self.indivi[i][1]!=None:
                F.add_arc(i,self.target,-self.indivi[i][1])

        for x,y,c in self.mutual:
            F.add_arc(x,y,c)

        alpha=F.max_flow(self.source,self.target)
        if Mode==0:
            return base-alpha
        else:
            return base-alpha,F.min_cut(self.source)[:self.N]

#==================================================
#Thansk for aaaaaaaaaa2230
#URL: https://atcoder.jp/contests/practice2/submissions/17017372

from collections import deque
class MaxFlow:
    inf = float("inf")

    class Arc:
        def __init__(self, to, cap, base, direction):
            self.to = to
            self.cap = cap
            self.base = base
            self.rev = None
            self.direction=direction

        def __repr__(self):
            if self.direction==1:
                return "[Source] (To: {}) {} / {}".format(self.to, self.cap,self.base)
            else:
                return "[Target] (From: {}) {} / {}".format(self.to, self.cap,self.base)

    def __init__(self, N):
        """ N 頂点のフロー場を生成する.
        """

        self.N=N
        self.arc = [[] for _ in range(N)]

    def add_arc(self, v, w, cap):
        """ 容量 cap の有向辺 v → w を加える.
        """

        a= self.Arc(w,cap,cap,1)
        a2 = self.Arc(v,0,cap,-1)
        a.rev = a2
        a2.rev = a
        self.arc[v].append(a)
        self.arc[w].append(a2)

    def add_edge(self, v, w, cap):
        """ 容量 cap の無向辺 v → w を加える."""
        self.add_arc(v,w,cap)
        self.add_arc(w,v,cap)

    def __bfs(self, s, t):
        level = self.level = [self.N]*self.N
        q = deque([s])
        level[s] = 0
        while q:
            now = q.popleft()
            lw = level[now]+1
            for a in self.arc[now]:
                if a.cap and level[a.to]> lw:
                    level[a.to] = lw
                    if a.to == t:
                        return True
                    q.append(a.to)
        return False

    def __dfs(self, s, t, up):
        arc = self.arc
        it = self.it
        level = self.level

        st = deque([t])
        while st:
            v = st[-1]
            if v == s:
                st.pop()
                flow = up
                for w in st:
                    a = arc[w][it[w]].rev
                    flow = min(flow, a.cap)
                for w in st:
                    a = arc[w][it[w]]
                    a.cap += flow
                    a.rev.cap -= flow
                return flow
            lv = level[v]-1
            while it[v] < len(arc[v]):
                a = arc[v][it[v]]
                ra = a.rev
                if ra.cap == 0 or lv != level[a.to]:
                    it[v] += 1
                    continue
                st.append(a.to)
                break
            if it[v] == len(arc[v]):
                st.pop()
                level[v] = self.N
        return 0

    def max_flow(self, source, target, flow_limit=inf):
        """ source から target に高々 flow_limit の水流を流すとき, "新たに流れる" 水流の大きさ"""

        flow = 0
        while flow < flow_limit and self.__bfs(source, target):
            self.it = [0]*self.N
            while flow < flow_limit:
                f = self.__dfs(source, target, flow_limit-flow)
                if f == 0:
                    break
                flow += f
        return flow

    def flow(self):
        """ 現在の フロー場に流れている各辺の流量を求める.

        """

        F=[{} for _ in range(self.N)]
        arc=self.arc
        for v in range(self.N):
            for a in arc[v]:
                if a.direction==1:
                    F[v][a.to]=a.base-a.cap
        return F

    def min_cut(self,s):
        """ s を 0 に含める最小カットを求める.
        """

        group = [1]*self.N
        Q = deque([s])
        while Q:
            v = Q.pop()
            group[v] = 0
            for a in self.arc[v]:
                if a.cap and group[a.to]:
                    Q.append(a.to)
        return group

#==================================================
N,M,K,P=map(int,input().split())
E=["*"]+list(map(int,input().split()))
F=["*"]+list(map(int,input().split()))
V=["*"]+list(map(int,input().split()))

L=[0]*(N+1)
A=[[] for _ in range(N+1)]
for i in range(1,N+1):
    L[i],*A[i]=list(map(int,input().split()))

I=[0]*(P+1); J=[0]*(P+1)
for p in range(1,P+1):
    I[p],J[p]=map(int,input().split())

#==================================================
H=Project_Selection_Problem(N+M+K+1)

for i in range(1,N+1):
    H.set_one(i,E[i])

    for l in A[i]:
        H.set_zero_one(N+M+l,i,-inf)

for j in range(1,M+1):
    H.set_zero(N+j,F[j])

for p in range(1,P+1):
    H.set_zero_one(N+J[p],I[p],-inf)

for k in range(1,K+1):
    H.set_one(N+M+k,-V[k])

#==================================================
C,R=H.solve(1)
X,Y,Z=R[1:N+1], R[N+1:N+M+1], R[N+M+1:N+M+K+1]
Y=[1-y for y in Y]

X=[0]+X; Y=[0]+Y; Z=[0]+Z

#==================================================
print(C)
print(sum(X)+sum(Y)+sum(Z))

for k in range(1,K+1):
    if Z[k]==1:
        print("Preparation",k)

for i in range(1,N+1):
    if X[i]==1:
        print("Goal",i)

for j in range(1,M+1):
    if Y[j]==1:
        print("Action",j)

yukicoder

結果

テストケース

ソースコード