結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
56,096 KB |
testcase_01 | AC | 40 ms
56,380 KB |
testcase_02 | AC | 38 ms
55,652 KB |
testcase_03 | AC | 129 ms
79,236 KB |
testcase_04 | AC | 130 ms
79,204 KB |
testcase_05 | AC | 131 ms
78,864 KB |
testcase_06 | AC | 130 ms
79,384 KB |
testcase_07 | AC | 133 ms
79,092 KB |
testcase_08 | AC | 161 ms
81,560 KB |
testcase_09 | AC | 123 ms
79,080 KB |
testcase_10 | AC | 87 ms
77,656 KB |
testcase_11 | AC | 111 ms
79,088 KB |
testcase_12 | AC | 176 ms
83,492 KB |
testcase_13 | AC | 52 ms
68,248 KB |
testcase_14 | AC | 119 ms
78,996 KB |
testcase_15 | AC | 50 ms
66,356 KB |
testcase_16 | AC | 50 ms
65,784 KB |
testcase_17 | AC | 126 ms
79,240 KB |
testcase_18 | AC | 119 ms
79,004 KB |
testcase_19 | AC | 129 ms
79,336 KB |
testcase_20 | AC | 116 ms
79,172 KB |
testcase_21 | AC | 113 ms
79,068 KB |
testcase_22 | AC | 117 ms
79,188 KB |
testcase_23 | AC | 121 ms
79,172 KB |
testcase_24 | AC | 123 ms
79,280 KB |
testcase_25 | AC | 125 ms
79,060 KB |
testcase_26 | AC | 1,438 ms
382,352 KB |
testcase_27 | AC | 286 ms
115,616 KB |
testcase_28 | AC | 194 ms
85,224 KB |
testcase_29 | AC | 184 ms
84,908 KB |
testcase_30 | AC | 91 ms
77,960 KB |
testcase_31 | AC | 38 ms
55,944 KB |
testcase_32 | AC | 38 ms
56,312 KB |
testcase_33 | AC | 1,264 ms
384,664 KB |
testcase_34 | AC | 1,314 ms
384,796 KB |
testcase_35 | AC | 1,382 ms
382,748 KB |
testcase_36 | AC | 969 ms
311,728 KB |
testcase_37 | AC | 200 ms
84,636 KB |
testcase_38 | AC | 288 ms
141,688 KB |
testcase_39 | AC | 166 ms
103,828 KB |
testcase_40 | AC | 188 ms
82,716 KB |
testcase_41 | AC | 210 ms
85,500 KB |
testcase_42 | AC | 43 ms
56,252 KB |
testcase_43 | AC | 38 ms
56,160 KB |
testcase_44 | AC | 38 ms
56,448 KB |
ソースコード
#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())