結果
| 問題 | No.1900 Don't be Powers of 2 |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2022-04-08 23:33:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,438 ms / 2,000 ms |
| コード長 | 8,628 bytes |
| コンパイル時間 | 410 ms |
| コンパイル使用メモリ | 82,384 KB |
| 実行使用メモリ | 384,796 KB |
| 最終ジャッジ日時 | 2024-11-28 14:46:15 |
| 合計ジャッジ時間 | 12,939 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 |
ソースコード
#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())