結果

問題 No.2523 Trick Flower
コンテスト
ユーザー norioc
提出日時 2026-10-05 18:03:53
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,724 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 65 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 378,652 KB
最終ジャッジ日時 2026-10-05 18:04:58
合計ジャッジ時間 41,673 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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 = sum(xs[v] for v in g)
        # 不足を次の SCC へ伝搬
        if x < 0:
            gset = set(g)
            moved = False
            for v in g:
                if moved: break

                for to in r_adj[v]:
                    if to in gset: continue

                    xs[to] += x  # 伝搬
                    moved = True
                    break

            if not moved:  # 不足を補えない
                return False

    return True


cc = scc(N, r_adj)
ans = bsearch(0, INF, can)
print(ans)
0