結果
問題 | No.1400 すごろくで世界旅行 |
ユーザー |
![]() |
提出日時 | 2021-02-19 22:30:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,651 ms / 3,153 ms |
コード長 | 3,413 bytes |
コンパイル時間 | 1,117 ms |
コンパイル使用メモリ | 117,196 KB |
実行使用メモリ | 21,760 KB |
最終ジャッジ日時 | 2024-09-16 20:37:47 |
合計ジャッジ時間 | 8,130 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <climits>#include <cmath>#include <complex>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <iomanip>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>#include <cstdint>using namespace std;typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;#define MP make_pair#define PB push_back#define inf 1000000007#define rep(i,n) for(int i = 0; i < (int)(n); ++i)#define all(x) (x).begin(),(x).end()template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T &val){std::fill( (T*)array, (T*)(array+N), val );}template<class T> inline bool chmax(T &a, T b){if(a<b){a = b;return true;}return false;}template<class T> inline bool chmin(T &a, T b){if(a>b){a = b;return true;}return false;}template <int COL_SIZE> class mat {private:// (or, and) の意味での積(正方かつ対称行列に限る(重みなし無向グラフの隣接行列とか))mat operator*(const mat& m) const {mat ans;for(int i = 0; i < COL_SIZE; i++){for(int j = 0; j < COL_SIZE; j++){if(this->a[i][j] == 0) continue;ans.a[i] |= m.a[j];}}return ans;}public:bitset<COL_SIZE>* a;int r;// 正方行列の場合mat() : mat(COL_SIZE){}// 一般の行列の場合mat(int row_size) : r(row_size){ a = new bitset<COL_SIZE>[r]; }int rank() const {int res = 0;mat<COL_SIZE> b(r);for(int i = 0; i < r; i++) b[i] = a[i];for(int i = 0; i < COL_SIZE; i++){if(res == r) return res;int pivot = res;if(!b[pivot][i]){for(int j = res + 1; j < r; j++){if(b[j][i]){pivot = j;break;}}if(!b[pivot][i]) continue;swap(b[pivot], b[res]);}for(int j = res + 1; j < r; j++){if(b[j][i]) b[j] ^= b[res];}res++;}return res;}inline const bitset<COL_SIZE>& operator[](size_t index) const {return a[index];}inline bitset<COL_SIZE>& operator[](size_t index){return a[index];}friend mat pow(mat m, long long cnt){mat res;for(int i = 0; i < COL_SIZE; i++) res[i][i] = 1;while(cnt){if(cnt & 1){res = res * m;}m = m * m;cnt >>= 1;}return res;}};int main(){mat<2000> M;int n;ll d;cin >> n >> d;rep(i,n){string s;cin >> s;rep(j,n){if(s[j]=='0'){M[i][j] = 0;}else{M[i][j] = 1;}}}if(d>=40000000)d = 40000000;mat<2000> X = pow(M,d);bool f = 1;rep(i,n){rep(j,n){if(!X[i][j])f = 0;}}if(f){cout << "Yes\n";}else{cout << "No\n";}return 0;}