結果
問題 | No.2523 Trick Flower |
ユーザー | MasKoaTS |
提出日時 | 2023-03-31 20:07:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 863 ms / 4,000 ms |
コード長 | 2,460 bytes |
コンパイル時間 | 1,039 ms |
コンパイル使用メモリ | 81,856 KB |
実行使用メモリ | 262,372 KB |
最終ジャッジ日時 | 2023-10-25 21:08:03 |
合計ジャッジ時間 | 13,261 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 34 ms
53,584 KB |
testcase_01 | AC | 35 ms
53,584 KB |
testcase_02 | AC | 34 ms
53,584 KB |
testcase_03 | AC | 34 ms
53,584 KB |
testcase_04 | AC | 34 ms
53,584 KB |
testcase_05 | AC | 33 ms
53,584 KB |
testcase_06 | AC | 33 ms
53,584 KB |
testcase_07 | AC | 35 ms
53,584 KB |
testcase_08 | AC | 77 ms
76,596 KB |
testcase_09 | AC | 72 ms
76,200 KB |
testcase_10 | AC | 49 ms
66,128 KB |
testcase_11 | AC | 53 ms
66,396 KB |
testcase_12 | AC | 51 ms
66,212 KB |
testcase_13 | AC | 66 ms
74,028 KB |
testcase_14 | AC | 64 ms
73,040 KB |
testcase_15 | AC | 824 ms
262,372 KB |
testcase_16 | AC | 863 ms
262,212 KB |
testcase_17 | AC | 280 ms
146,548 KB |
testcase_18 | AC | 233 ms
132,892 KB |
testcase_19 | AC | 657 ms
223,456 KB |
testcase_20 | AC | 662 ms
258,720 KB |
testcase_21 | AC | 656 ms
256,648 KB |
testcase_22 | AC | 672 ms
260,716 KB |
testcase_23 | AC | 675 ms
216,720 KB |
testcase_24 | AC | 457 ms
196,528 KB |
testcase_25 | AC | 571 ms
259,668 KB |
testcase_26 | AC | 538 ms
240,236 KB |
testcase_27 | AC | 621 ms
259,756 KB |
testcase_28 | AC | 505 ms
221,996 KB |
testcase_29 | AC | 182 ms
106,804 KB |
testcase_30 | AC | 464 ms
220,744 KB |
testcase_31 | AC | 120 ms
79,180 KB |
testcase_32 | AC | 325 ms
166,280 KB |
testcase_33 | AC | 615 ms
260,456 KB |
ソースコード
import sys input = sys.stdin.readline class SCC: def __init__(self, n): self.n = n self.graph = [[] for _ in range(n)] self.rev_graph = [[] for _ in range(n)] self.labels = [-1] * n self.lb_cnt = 0 def add_edge(self, v, nxt_v): self.graph[v].append(nxt_v) self.rev_graph[nxt_v].append(v) def build(self): self.post_order = [] self.used = [False] * self.n for v in range(self.n): if(self.used[v]): continue self._dfs(v) for v in reversed(self.post_order): if(self.labels[v] != -1): continue self._rev_dfs(v) self.lb_cnt += 1 def _dfs(self, v): stack = [v, 0] while(stack): v, idx = stack[-2:] if(not(idx) and self.used[v]): stack.pop() stack.pop() else: self.used[v] = True if(idx < len(self.graph[v])): stack[-1] += 1 stack.append(self.graph[v][idx]) stack.append(0) else: stack.pop() self.post_order.append(stack.pop()) def _rev_dfs(self, v): stack = [v] self.labels[v] = self.lb_cnt while stack: v = stack.pop() for nxt_v in self.rev_graph[v]: if(self.labels[nxt_v] != -1): continue stack.append(nxt_v) self.labels[nxt_v] = self.lb_cnt def construct(self): self.dag = [[] for i in range(self.lb_cnt)] self.groups = [[] for i in range(self.lb_cnt)] for v, lb in enumerate(self.labels): for nxt_v in self.graph[v]: nxt_lb = self.labels[nxt_v] if(lb == nxt_lb): continue self.dag[lb].append(nxt_lb) self.groups[lb].append(v) return self.dag, self.groups """ Main Code """ N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) c = list(map(int, input().split())) scc = SCC(N) for i, k in enumerate(c): if(i == k - 1): continue scc.add_edge(k - 1, i) scc.build() dag, groups = scc.construct() n = len(groups) a = [0] * n b = [0] * n for i, g in enumerate(groups): a[i] = sum(A[k] for k in g) b[i] = sum(B[k] for k in g) rdag = [[] for _ in [0] * n] for i, lis in enumerate(dag): for v in lis: rdag[v].append(i) def check(mid): visited = set([]) dp = [aa - mid * bb for aa, bb in zip(a, b)] for x in range(n - 1, -1, -1): if(x in visited): continue visited.add(x) if(dp[x] > 0): dp[x] = 0 if(not(rdag[x]) and dp[x] < 0): return False for y in rdag[x]: dp[y] += dp[x] return True ok = 0 ng = sum(a) // sum(b) + 1 while(ng - ok > 1): mid = (ok + ng) >> 1 if(check(mid)): ok = mid else: ng = mid print(ok)