結果

問題 No.1900 Don't be Powers of 2
ユーザー 👑 KazunKazun
提出日時 2022-04-08 23:33:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,296 ms / 2,000 ms
コード長 8,628 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 86,776 KB
実行使用メモリ 384,648 KB
最終ジャッジ日時 2023-08-19 02:06:37
合計ジャッジ時間 14,036 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
72,180 KB
testcase_01 AC 76 ms
72,532 KB
testcase_02 AC 76 ms
72,456 KB
testcase_03 AC 163 ms
80,852 KB
testcase_04 AC 153 ms
80,740 KB
testcase_05 AC 157 ms
80,612 KB
testcase_06 AC 155 ms
80,668 KB
testcase_07 AC 153 ms
80,856 KB
testcase_08 AC 183 ms
84,352 KB
testcase_09 AC 148 ms
81,008 KB
testcase_10 AC 118 ms
78,980 KB
testcase_11 AC 142 ms
79,388 KB
testcase_12 AC 200 ms
85,404 KB
testcase_13 AC 90 ms
77,752 KB
testcase_14 AC 143 ms
80,616 KB
testcase_15 AC 86 ms
77,608 KB
testcase_16 AC 86 ms
77,552 KB
testcase_17 AC 151 ms
81,024 KB
testcase_18 AC 148 ms
80,424 KB
testcase_19 AC 161 ms
80,772 KB
testcase_20 AC 145 ms
80,548 KB
testcase_21 AC 144 ms
80,260 KB
testcase_22 AC 141 ms
80,268 KB
testcase_23 AC 145 ms
80,788 KB
testcase_24 AC 147 ms
80,812 KB
testcase_25 AC 148 ms
80,916 KB
testcase_26 AC 1,296 ms
380,568 KB
testcase_27 AC 309 ms
116,612 KB
testcase_28 AC 211 ms
86,956 KB
testcase_29 AC 209 ms
86,528 KB
testcase_30 AC 124 ms
79,436 KB
testcase_31 AC 79 ms
72,216 KB
testcase_32 AC 78 ms
72,444 KB
testcase_33 AC 1,185 ms
384,576 KB
testcase_34 AC 1,200 ms
384,648 KB
testcase_35 AC 1,256 ms
381,544 KB
testcase_36 AC 883 ms
317,768 KB
testcase_37 AC 219 ms
85,792 KB
testcase_38 AC 314 ms
143,868 KB
testcase_39 AC 195 ms
105,588 KB
testcase_40 AC 212 ms
83,320 KB
testcase_41 AC 231 ms
86,064 KB
testcase_42 AC 77 ms
72,000 KB
testcase_43 AC 78 ms
72,588 KB
testcase_44 AC 77 ms
72,156 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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]
#==================================================
#==================================================
N=int(input())
A=list(map(int,input().split()))

W=30
S=set(1<<i for i in range(W))

E=[[] for _ in range(N+1)]
for i in range(N):
    for j in range(i,N):
        if (A[i]^A[j] in S):
            E[i].append(j)
            E[j].append(i)

T=[-1]*N
for i in range(N):
    if T[i]!=-1:
        continue

    T[i]=0
    Q=[i]
    while Q:
        i=Q.pop()
        for j in E[i]:
            if T[j]==-1:
                T[j]=1-T[i]
                Q.append(j)

P=Project_Selection_Problem(N)
for i in range(N):
    if T[i]==1:
        P.set_one(i,1)
        for j in E[i]:
            P.set_zero_one(j,i,-inf)
    else:
        P.set_zero(i,1)

print(P.solve())
0