結果

問題 No.2523 Trick Flower
コンテスト
ユーザー norioc
提出日時 2026-10-25 22:46:45
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,611 ms / 4,000 ms
+ 545µs
コード長 1,696 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 91 ms
コンパイル使用メモリ 64,656 KB
実行使用メモリ 235,656 KB
最終ジャッジ日時 2026-10-30 12:57:49
合計ジャッジ時間 20,740 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
from atcoder.scc import SCCGraph


def bsearch(low: int, high: int, pred) -> int:
    assert pred(low)
    lo = low
    hi = high
    res = low
    while lo <= hi:
        m = (lo + hi) // 2
        if pred(m):
            res = max(res, m)
            lo = m + 1
        else:
            hi = m - 1

    return res


def scc(n: int, adj: dict[int, list[int]]) -> list[list[int]]:
    """グラフを強連結成分分解する。

    Args:
        n: 頂点数
        adj: 隣接リスト {u: [v...]}

    Returns:
        強連結成分のリスト (トポロジカル順)
    """

    g = SCCGraph(n)
    for u, vs in adj.items():
        for v in vs:
            g.add_edge(u, v)

    return g.scc()


INF = 1 << 62
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(lambda x: int(x)-1, input().split()))

r_adj = defaultdict(list)  # 逆辺
for i, c in enumerate(C):
    r_adj[i].append(c)


# m 本作れるか
def can(m: int) -> bool:
    xs = [a - b * m for a, b in zip(A, B)]  # 本数の余り(不足)

    # Functional Graph で本数の不足を伝搬していく
    for g in cc:
        x = 0
        for v in g:
            x += xs[v]

        # 不足を次の SCC へ伝搬
        if x < 0:
            gset = set(g)
            for v in g:
                for to in r_adj[v]:
                    if to in gset: continue

                    xs[to] += x  # 伝搬
                    break
                else:
                    # 伝搬できない
                    return False

    return True


cc = scc(N, r_adj)
high = sum(A) // sum(B)
ans = bsearch(0, high, can)
print(ans)
0