結果
問題 | No.1340 おーじ君をさがせ |
ユーザー |
|
提出日時 | 2021-01-15 23:18:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,533 bytes |
コンパイル時間 | 1,548 ms |
コンパイル使用メモリ | 168,976 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-11-27 23:21:00 |
合計ジャッジ時間 | 3,672 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)#define chmin(x,y) x = min((x),(y));#define chmax(x,y) x = max((x),(y));using namespace std;using ll = long long ;using P = pair<int,int> ;using pll = pair<long long,long long>;const int INF = 1e9;const long long LINF = 1e17;const int MOD = 1000000007;//const int MOD = 998244353;const double PI = 3.14159265358979323846;int G[105][105];int doubling[66][105][105];// 1<<i回でj->kに行けるint main(){int n,m;ll t;cin >> n >> m >> t;rep(i,m){int a,b;cin >> a >> b;doubling[0][a][b] = 1;}for(int i=0;i<65;i++){rep(j,n){rep(k,n){// doubling[i+1][j][k]rep(l,n){if(doubling[i][j][l] == 1 && doubling[i][l][k] == 1){doubling[i+1][j][k] = 1;break;}}}}}vector<int> been(n,0);been[0] = 1;int c = 0;while(t > 0){if(t&1){vector<int> nxt(n,0);rep(i,n){if(been[i]==1){rep(j,n){if(doubling[c][i][j] == 1){nxt[j] = 1;}}}}swap(been,nxt);}t >>= 1;++c;}int sum = 0;rep(i,n) sum += (been[i]==1);cout << sum << endl;return 0;}