結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2023-01-22 13:45:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,688 ms / 2,000 ms |
コード長 | 2,140 bytes |
コンパイル時間 | 283 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 81,280 KB |
最終ジャッジ日時 | 2024-06-24 18:34:02 |
合計ジャッジ時間 | 15,724 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
def oi(): return int(input())def os(): return input()def mi(): return list(map(int, input().split()))import sysinput = sys.stdin.readline# import sys# sys.setrecursionlimit(10**8)# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')input_count = 0def prod_func(a,b):if a*b > 0:return 1return 0def add_func(a,b):return a+bclass MATRIX:def __init__(self, prod_func, add_func):self.prod_func = prod_funcself.add_func = add_funcdef dot(self, A,B):if len(A[0]) != len(B):return Noneout = [[0] * len(B[0]) for _ in range(len(A))]for ay in range(len(A)):for bx in range(len(B[0])):sums = 0for ax in range(len(A[0])):sums += self.prod_func(A[ay][ax], B[ax][bx])out[ay][bx] = sumsreturn outdef sum(self, A,B):if not(len(A) == len(B) and len(A[0]) == len(B[0])):return Noneout = []for ay in range(len(A)):temp = []for ax in range(len(A[0])):temp.append(self.add_func(A[ay][ax], B[ay][ax]))out.append(temp)return outdef prod(self, A,B):if not(len(A) == len(B) and len(A[0]) == len(B[0])):return Noneout = []for ay in range(len(A)):temp = []for ax in range(len(A[0])):temp.append(self.prod_func(A[ay][ax], B[ay][ax]))out.append(temp)return out# 正方行列AをN乗する。def ruijou(self, A, N):out = [[0] * len(A) for _ in range(len(A))]for i in range(len(A)):out[i][i] = 1while N:if N%2==1:out = self.dot(out, A)A = self.dot(A,A)N//=2return outinput_count = 0N,M,T = mi()mat = [[0] * N for _ in range(N)]MAT = MATRIX(prod_func, add_func)for i in range(M):a,b = mi()mat[a][b] = 1out = MAT.ruijou(mat, T)count = 0for o in out[0]:if o>0:count += 1print(count)