結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-02-12 17:41:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 602 ms / 2,000 ms |
コード長 | 744 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,668 KB |
実行使用メモリ | 81,016 KB |
最終ジャッジ日時 | 2024-07-19 12:14:27 |
合計ジャッジ時間 | 10,440 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
def dot(mtr0,mtr1):a,b=len(mtr0),len(mtr1[0])t=len(mtr0[0])if t!=len(mtr1):return Noneret=[[0]*b for _ in range(a)]for i in range(a):for j in range(b):tmp=0for k in range(t):tmp+=mtr0[i][k]*mtr1[k][j]if tmp>0:tmp=1ret[i][j]=tmpreturn retdef main0(n,m,t,ab):# ダブリング。O(n^2)g=[[0]*n for _ in range(n)]for a,b in ab:g[b][a]=1vc=[[0] for _ in range(n)]vc[0][0]=1while t:if t%2==1:vc=dot(g,vc)g=dot(g,g)t>>=1ans=0for i in range(n):if vc[i][0]==1:ans+=1return ansif __name__=='__main__':n,m,t=map(int,input().split())ab=[list(map(int,input().split())) for _ in range(m)]ret0=main0(n,m,t,ab)print(ret0)