結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2020-09-26 15:12:11 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 836 bytes |
コンパイル時間 | 82 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 44,496 KB |
最終ジャッジ日時 | 2024-11-26 19:23:55 |
合計ジャッジ時間 | 33,068 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 46 WA * 11 RE * 2 |
ソースコード
"""bit並列化"""import sysimport numpy as npread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesK = 60def mult(A, B):N = len(A)C = np.zeros_like(A)# A[i,j] == 1 のとき、 C[i,:] |= B[j,:] となるのでfor j in range(N):add_to = (A[:, j // K] & (1 << j % K)) > 0C |= add_to[:,None] * B[j]return Cdef mat_pow(A, n):N = len(A)if n == 1:return AX = mat_pow(A, n // 2)X = mult(X, X)return mult(A, X) if n & 1 else XN, M, T = map(int, readline().split())A = np.zeros((N, N // K + 1), np.int64)m = map(int, read().split())for frm, to in zip(m, m):A[frm, to // K] |= 1 << to % KB = mat_pow(A, T)ans = 0for x in B[0]:ans += bin(x).count('1')if not ans:ans = -1print(ans)