結果

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

ソースコード

diff #
raw source code 

from collections import defaultdict, deque
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()))

adj = defaultdict(list)
for i, c in enumerate(C):
    adj[c].append(i)


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

    # Functional Graph で交換可能な本数の余り(不足)を伝搬していく
    for g in cc:
        gset = set(g)
        x = 0
        for v in g:
            x += xs[v]
            xs[v] = 0

        xs[g[0]] = x  # 一カ所にまとめる
        # 花が余っているなら(x > 0)、次の SCC へ伝搬
        if x <= 0: continue
        moved = False
        for v in g:
            if moved: break

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

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

    return all(x >= 0 for x in xs)  # 全ノードで不足が存在しない


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