結果
問題 | No.2523 Trick Flower |
ユーザー | chineristAC |
提出日時 | 2023-10-27 21:40:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,253 ms / 4,000 ms |
コード長 | 1,694 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 81,832 KB |
実行使用メモリ | 261,036 KB |
最終ジャッジ日時 | 2023-10-27 21:40:59 |
合計ジャッジ時間 | 19,056 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
56,292 KB |
testcase_01 | AC | 40 ms
56,292 KB |
testcase_02 | AC | 40 ms
56,292 KB |
testcase_03 | AC | 43 ms
56,292 KB |
testcase_04 | AC | 39 ms
56,292 KB |
testcase_05 | AC | 40 ms
56,292 KB |
testcase_06 | AC | 44 ms
56,292 KB |
testcase_07 | AC | 48 ms
64,540 KB |
testcase_08 | AC | 72 ms
76,904 KB |
testcase_09 | AC | 76 ms
76,992 KB |
testcase_10 | AC | 55 ms
68,660 KB |
testcase_11 | AC | 60 ms
73,192 KB |
testcase_12 | AC | 57 ms
68,680 KB |
testcase_13 | AC | 73 ms
77,132 KB |
testcase_14 | AC | 72 ms
76,976 KB |
testcase_15 | AC | 531 ms
144,608 KB |
testcase_16 | AC | 497 ms
143,884 KB |
testcase_17 | AC | 687 ms
261,036 KB |
testcase_18 | AC | 530 ms
229,072 KB |
testcase_19 | AC | 1,063 ms
143,708 KB |
testcase_20 | AC | 1,079 ms
143,812 KB |
testcase_21 | AC | 1,145 ms
143,572 KB |
testcase_22 | AC | 1,072 ms
143,708 KB |
testcase_23 | AC | 1,171 ms
143,728 KB |
testcase_24 | AC | 604 ms
113,292 KB |
testcase_25 | AC | 967 ms
133,488 KB |
testcase_26 | AC | 1,010 ms
134,552 KB |
testcase_27 | AC | 1,186 ms
142,148 KB |
testcase_28 | AC | 814 ms
122,852 KB |
testcase_29 | AC | 209 ms
84,852 KB |
testcase_30 | AC | 870 ms
117,884 KB |
testcase_31 | AC | 113 ms
79,124 KB |
testcase_32 | AC | 409 ms
100,100 KB |
testcase_33 | AC | 1,253 ms
144,748 KB |
ソースコード
import sys from itertools import permutations import heapq from collections import deque import random input = 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: continue t = len(comp_cycle) tmp = [i] while True: nxt = C[tmp[-1]] if nxt!=i: tmp.append(nxt) else: break for v in tmp: comp_cycle[v] = t comp_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] * n for i in range(N): if comp_cycle[i]!=i: continue parent[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] * n def 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] = 0 for root in range(N,n): if dp[root]: return False return True ok = 0 ng = 10**15 + 1 while ng-ok>1: mid = (ok+ng)//2 if cond(mid): ok = mid else: ng = mid print(ok)