結果
問題 | No.1400 すごろくで世界旅行 |
ユーザー |
![]() |
提出日時 | 2021-02-19 22:46:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,916 ms / 3,153 ms |
コード長 | 1,693 bytes |
コンパイル時間 | 4,075 ms |
コンパイル使用メモリ | 205,236 KB |
最終ジャッジ日時 | 2025-01-19 01:05:07 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000000int main(){int V;cin>>V;long long D;cin>>D;if(D>Inf){D = Inf + (D&1);D -= 10;}vector<string> S(V);rep(i,V)cin>>S[i];vector<int> remain(V);rep(i,V){remain[i] = i;}mt19937 rnd(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());auto start = chrono::system_clock::now();while(remain.size()>0){if(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() > 2800){cout<<"Yes"<<endl;return 0;}int ind = rnd() % remain.size();vector<int> d(V*2,Inf);queue<int> Q;Q.push(remain[ind]*2);while(Q.size()>0){int u = Q.front()>>1;int b = Q.front()&1;Q.pop();rep(i,V){if(S[u][i]=='0')continue;int v = i;int nb = b^1;if(d[v*2+nb]!=Inf)continue;int t = d[u*2+b];if(t==Inf)t = 0;d[v*2+nb] = t+1;Q.push(v*2+nb);}}bool f = true;rep(i,V){if(d[i*2+(D&1)]>D){f=false;break;}}if(!f)break;vector<bool> ok(V,false);ok[remain[ind]] = true;rep(i,V){bool F = true;rep(j,V){bool F2 = false;rep(k,2){int x = i*2 + k,y = j*2 + (k^(D&1));if(d[x]+d[y]<=D){F2 = true;break;}}if(!F2){F=false;break;}}if(F)ok[i] = true;}vector<int> nr;rep(i,remain.size()){if(!ok[remain[i]])nr.push_back(remain[i]);}swap(remain,nr);}if(remain.size()==0)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;}