結果
問題 | No.2523 Trick Flower |
ユーザー |
|
提出日時 | 2023-10-27 21:40:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,364 ms / 4,000 ms |
コード長 | 1,694 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 261,348 KB |
最終ジャッジ日時 | 2024-09-25 13:45:50 |
合計ジャッジ時間 | 20,106 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
import sysfrom itertools import permutationsimport heapqfrom collections import dequeimport randominput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N = int(input())A = li()B = li()C = li()C = [c-1 for c in C]cycle = [C[i] for i in range(N)]for _ in range(30):cycle = [cycle[cycle[i]] for i in range(N)]cycle = set(cycle)comp_cycle = [i for i in range(N)]for i in range(N):if i not in cycle or comp_cycle[i]!=i:continuet = len(comp_cycle)tmp = [i]while True:nxt = C[tmp[-1]]if nxt!=i:tmp.append(nxt)else:breakfor v in tmp:comp_cycle[v] = tcomp_cycle.append(t)A.append(sum([A[i] for i in tmp]))B.append(sum([B[i] for i in tmp]))n = len(comp_cycle)edge = [[] for v in range(n)]parent = [-1] * nfor i in range(N):if comp_cycle[i]!=i:continueparent[comp_cycle[i]] = comp_cycle[C[i]]edge[comp_cycle[C[i]]].append(comp_cycle[i])topo = []for root in range(N,n):deq = deque([root])while deq:v = deq.popleft()topo.append(v)for nv in edge[v]:deq.append(nv)dp = [-1] * ndef cond(k):for v in topo[::-1]:dp[v] = k * B[v]for nv in edge[v]:dp[v] += dp[nv]if dp[v] > A[v]:dp[v] -= A[v]else:dp[v] = 0for root in range(N,n):if dp[root]:return Falsereturn Trueok = 0ng = 10**15 + 1while ng-ok>1:mid = (ok+ng)//2if cond(mid):ok = midelse:ng = midprint(ok)