結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
![]() |
提出日時 | 2020-09-22 01:15:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 957 bytes |
コンパイル時間 | 2,500 ms |
コンパイル使用メモリ | 199,752 KB |
最終ジャッジ日時 | 2025-01-14 19:26:22 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 48 WA * 11 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;using namespace std;int n;vector<vector<int> > mul(vector<vector<int> > a, vector<vector<int> > b){vector<vector<int> > ret(n, vector<int> (n, 0));for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)ret[i][j] |= a[i][k] & b[k][j];return ret;}vector<vector<int> > pow(vector<vector<int> > a, ll t){vector<vector<int> > ret(n, vector<int> (n, 0));for(int i=0;i<n;i++) ret[i][i] = 1;while(t > 0){if(t & 1) ret = mul(ret, a);a = mul(a, a);t >>= 1;}return ret;}int main() {ll m, t;cin >> n >> m >> t;vector<vector<int> > G(n, vector<int> (n, 0));int a, b;for(int i=0;i<m;i++){cin >> a >> b;G[b][a] = 1;}G = pow(G, t);int ans = 0;for(int i=0;i<n;i++) ans += G[i][0];cout << (ans ? ans : -1) << endl;return 0;}