結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-16 22:37:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,160 bytes |
コンパイル時間 | 1,913 ms |
コンパイル使用メモリ | 174,128 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 08:47:33 |
合計ジャッジ時間 | 4,597 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); i++)using namespace std;typedef long long ll;vector<vector<long long>> matmul(vector<vector<long long>> A, vector<vector<long long>> B){int N = A.size();vector<vector<long long>> ans(N, vector<long long>(N, 0));for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){for (int k = 0; k < N; k++){ans[i][k] |= A[i][j] & B[j][k];}}}return ans;}vector<vector<long long>> matpow(vector<vector<long long>> A, long long b){int N = A.size();vector<vector<long long>> ans(N, vector<long long>(N, 0));for (int i = 0; i < N; i++){ans[i][i] = 1;}while (b > 0){if (b % 2 == 1){ans = matmul(ans, A);}A = matmul(A, A);b /= 2;}return ans;}int main(){cin.tie(0);ios::sync_with_stdio(0);ll N,M,T; cin >> N >> M >> T;vector<vector<ll>> A(N, vector<ll> (N, 0));rep(i,M){ll a,b; cin >> a >> b;A[a][b] = 1;}A = matpow(A, T);int ans = 0;rep(i,N) ans += A[0][i];cout << ans << '\n';}