結果
問題 |
No.2948 move move rotti
|
ユーザー |
![]() |
提出日時 | 2024-10-25 21:51:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 301 ms / 4,000 ms |
コード長 | 1,108 bytes |
コンパイル時間 | 2,112 ms |
コンパイル使用メモリ | 199,768 KB |
最終ジャッジ日時 | 2025-02-24 23:00:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; int n,m,k; int x[15]; vector<int> g[15]; int main(){ cin>>n>>m>>k; for(int i=0;i<k;i++)cin>>x[i]; for(int i=0;i<m;i++){ int u,v;cin>>u>>v;u--;v--; g[u].push_back(v); g[v].push_back(u); } vector<vector<int>> dp(k,vector<int>(n<<n)); vector<vector<int>> ok(k,vector<int>(n*n)); for(int i=0;i<k;i++){ x[i]--; dp[i][(1<<x[i])*n+x[i]]=1; ok[i][x[i]*n+1]=1; for(int j=0;j<(n<<n);j++){ if(dp[i][j]==0)continue; int s=j/n; for(auto l:g[j%n]){ if(s>>l&1)continue; dp[i][(s|(1<<l))*n+l]=1; ok[i][l*n+__builtin_popcount(s)+1]=1; } } // cout<<"i:"<<i<<"\n"; // for(int j=0;j<(n<<n);j++){ // cout<<j%n<<" "<<(bitset<5>(j/n))<<" "<<dp[i][j]<<"\n"; // } } for(int i=0;i<n*n;i++){ bool fl=true; for(int j=0;j<k;j++)fl&=ok[j][i]; if(fl){ cout<<"Yes\n"; return 0; } } cout<<"No\n"; }