結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-16 05:50:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 1,868 bytes |
コンパイル時間 | 2,489 ms |
コンパイル使用メモリ | 203,636 KB |
最終ジャッジ日時 | 2025-01-17 21:17:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
/*** author: otera**/#include<bits/stdc++.h>using namespace std;#define int long longtypedef long long ll;typedef long double ld;const int inf=1e9+7;const ll INF=1LL<<60;#define rep(i, n) for(int i = 0; i < n; ++ i)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)typedef pair<int, int> P;typedef pair<ll, ll> LP;#define fr first#define sc second#define all(c) c.begin(),c.end()template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b) {int sz = (int)a.size();vector<vector<int>> ret(sz, vector<int>(sz, 0));rep(i, sz) {rep(j, sz) {rep(k, sz) {ret[i][k] |= (a[i][j] & b[j][k]);}}}return ret;}vector<vector<int>> pw(vector<vector<int>> a, ll n) {int sz = (int)a.size();if(n == 0) {vector<vector<int>> ret(sz, vector<int>(sz, 0));rep(i, sz) {ret[i][i] = 1LL;}return ret;}vector<vector<int>> ret = pw(mul(a, a), n / 2);if(n & 1) ret = mul(ret, a);return ret;}void solve() {int n, m; ll t; cin >> n >> m >> t;vector<vector<int>> g(n, vector<int>());vector<vector<int>> d(n, vector<int>(n, 0));rep(i, m) {int a, b; cin >> a >> b;g[a].push_back(b);d[a][b] = 1;}d = pw(d, t);int cnt = 0;rep(i, n) {if(d[0][i]) {cerr << i << endl;++ cnt;}}cout << cnt << "\n";}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(20);//int t; cin >> t; rep(i, t)solve();solve();return 0;}