結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:35:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,715 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 77,356 KB
最終ジャッジ日時 2025-03-31 17:36:33
合計ジャッジ時間 5,136 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    T = int(data[idx])
    idx += 1

    out_degree = [0] * n
    matrix = [0] * n

    for _ in range(m):
        a = int(data[idx])
        idx += 1
        b = int(data[idx])
        idx += 1
        matrix[a] |= 1 << b
        out_degree[a] += 1

    def pow_matrix_vector(A, power, n):
        if power == 0:
            return 1 << 0  # Initial position is vertex 0

        result = 1 << 0  # Start at vertex 0
        current_op = A.copy()

        while power > 0:
            if power % 2 == 1:
                new_result = 0
                mask = result
                u = 0
                while mask and u < n:
                    if mask & 1:
                        new_result |= current_op[u]
                    mask >>= 1
                    u += 1
                result = new_result

            # Square the current operator
            new_current = [0] * n
            for u in range(n):
                row = current_op[u]
                val = 0
                bits = row
                v = 0
                while bits and v < n:
                    if bits & 1:
                        val |= current_op[v]
                    bits >>= 1
                    v += 1
                new_current[u] = val
            current_op = new_current
            power //= 2

        return result

    reachable_mask = pow_matrix_vector(matrix, T, n)

    count = 0
    for u in range(n):
        if (reachable_mask & (1 << u)) and out_degree[u] > 0:
            count += 1

    print(count)

if __name__ == '__main__':
    main()
0