結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:52:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,992 ms / 2,000 ms
コード長 2,331 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 85,664 KB
最終ジャッジ日時 2025-04-15 21:53:53
合計ジャッジ時間 10,243 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

def multiply(mat_a, mat_b):
    n = len(mat_a)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if mat_a[i][k]:
                for j in range(n):
                    if mat_b[k][j]:
                        result[i][j] = 1
    return result

def matrix_power(mat, power):
    n = len(mat)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        result[i][i] = 1
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, mat)
        mat = multiply(mat, mat)
        power //= 2
    return result

def multiply_vector(vec, mat):
    n = len(vec)
    new_vec = [0] * n
    for j in range(n):
        for i in range(n):
            if vec[i] and mat[i][j]:
                new_vec[j] = 1
                break
    return new_vec

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    T = int(input[idx]); idx +=1

    adj = [[] for _ in range(N)]
    out_degree = [0] * N
    for _ in range(M):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        adj[a].append(b)
        out_degree[a] +=1

    if T == 0:
        print(1)
        return

    # Construct transition matrix A
    A = [[0]*N for _ in range(N)]
    for u in range(N):
        if out_degree[u] > 0:
            for v in adj[u]:
                A[u][v] = 1

    # Compute part1: after T steps, vertices with out_degree >0
    AT = matrix_power(A, T)
    vec_T = [0]*N
    vec_T[0] = 1
    vec_T = multiply_vector(vec_T, AT)
    part1 = sum(1 for v in range(N) if vec_T[v] and out_degree[v] > 0)

    # Compute part2: after T-1 steps, u has out_degree >0 and u->v where v has out_degree 0
    part2 = 0
    if T >= 1:
        AT_minus_1 = matrix_power(A, T-1)
        vec_T_minus_1 = [0]*N
        vec_T_minus_1[0] = 1
        vec_T_minus_1 = multiply_vector(vec_T_minus_1, AT_minus_1)
        part2_set = set()
        for u in range(N):
            if vec_T_minus_1[u] and out_degree[u] > 0:
                for v in adj[u]:
                    if out_degree[v] == 0:
                        part2_set.add(v)
        part2 = len(part2_set)
    else:
        part2 = 0

    total = part1 + part2
    print(total)

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