結果
問題 | No.2523 Trick Flower |
ユーザー | titia |
提出日時 | 2023-11-09 03:07:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,281 ms / 4,000 ms |
コード長 | 2,370 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 278,064 KB |
最終ジャッジ日時 | 2023-11-09 03:07:35 |
合計ジャッジ時間 | 8,650 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,460 KB |
testcase_01 | AC | 36 ms
53,460 KB |
testcase_02 | AC | 36 ms
53,460 KB |
testcase_03 | AC | 36 ms
53,460 KB |
testcase_04 | AC | 47 ms
53,460 KB |
testcase_05 | AC | 36 ms
53,460 KB |
testcase_06 | AC | 36 ms
53,460 KB |
testcase_07 | AC | 50 ms
64,324 KB |
testcase_08 | AC | 96 ms
76,640 KB |
testcase_09 | AC | 99 ms
76,636 KB |
testcase_10 | AC | 41 ms
55,596 KB |
testcase_11 | AC | 64 ms
70,712 KB |
testcase_12 | AC | 64 ms
71,136 KB |
testcase_13 | AC | 93 ms
76,472 KB |
testcase_14 | AC | 97 ms
76,532 KB |
testcase_15 | AC | 3,281 ms
185,744 KB |
testcase_16 | AC | 3,216 ms
183,244 KB |
testcase_17 | AC | 1,215 ms
278,064 KB |
testcase_18 | AC | 225 ms
162,644 KB |
testcase_19 | AC | 1,912 ms
178,432 KB |
testcase_20 | AC | 2,263 ms
181,124 KB |
testcase_21 | AC | 2,811 ms
186,368 KB |
testcase_22 | AC | 1,326 ms
184,700 KB |
testcase_23 | AC | 1,565 ms
178,176 KB |
testcase_24 | AC | 1,231 ms
131,912 KB |
testcase_25 | AC | 848 ms
169,164 KB |
testcase_26 | AC | 2,741 ms
179,704 KB |
testcase_27 | AC | 1,998 ms
174,720 KB |
testcase_28 | AC | 2,150 ms
166,320 KB |
testcase_29 | AC | 196 ms
99,900 KB |
testcase_30 | AC | 1,189 ms
146,656 KB |
testcase_31 | AC | 172 ms
81,304 KB |
testcase_32 | AC | 342 ms
120,732 KB |
testcase_33 | AC | 1,856 ms
175,148 KB |
ソースコード
N=int(input()) A=list(map(int,input().split())) B=list(map(int,input().split())) C=list(map(int,input().split())) for i in range(N): C[i]-=1 # (一般グラフの)トポロジカルソート、SCC E=[[] for i in range(N)] E_INV=[[] for i in range(N)] for i in range(N): E_INV[C[i]].append(i) E[i].append(C[i]) # DFSして帰り際にTOPに点を放り込んでいる。 # NOWで現在地点、USEINDで、どこの辺まで既に見たか、を調べている。 def Top_sort(E): Parent=[-1]*N USEIND=[0]*N TOP=[] for ROOT in range(N): if Parent[ROOT]!=-1: continue Parent[ROOT]=ROOT NOW=ROOT while NOW!=ROOT or USEIND[ROOT]!=len(E[ROOT]): if USEIND[NOW]==len(E[NOW]): TOP.append(NOW) NOW=Parent[NOW] elif E[NOW][USEIND[NOW]]==Parent[NOW]: USEIND[NOW]+=1 else: NEXT=E[NOW][USEIND[NOW]] USEIND[NOW]+=1 if Parent[NEXT]==-1: Parent[NEXT]=NOW NOW=NEXT TOP.append(ROOT) return TOP[::-1] USE=[0]*N SCC=[] # SCCを調べるための逆順DFS。 # やっていることはhttps://manabitimes.jp/math/1250 などと同じ。 def dfs2(x): Q=[x] USE[x]=1 ANS=[] while Q: x=Q.pop() ANS.append(x) for to in E_INV[x]: if USE[to]==0: USE[to]=1 Q.append(to) return ANS TOP_SORT=Top_sort(E) for x in TOP_SORT: if USE[x]==0: SCC.append(dfs2(x)) REP=[-1]*N for scc in SCC: rep=scc[0] for s in scc: REP[s]=rep E_INV=[set() for i in range(N)] E=[set() for i in range(N)] for i in range(N): if REP[C[i]]!=REP[i]: E_INV[REP[C[i]]].add(REP[i]) E[REP[i]].add(REP[C[i]]) OK=0 NG=10**15 while NG>OK+1: mid=(OK+NG)//2 rest=0 flag=1 DP=[0]*N for i in range(len(SCC)): need=0 for sc in SCC[i]: need+=B[sc]*mid-A[sc] for fr in E_INV[SCC[i][0]]: need+=DP[fr] if need>0 and E[SCC[i][0]]==set(): flag=0 break else: if need>0: DP[SCC[i][0]]=need if flag==1: OK=mid else: NG=mid print(OK)