結果
問題 | No.2948 move move rotti |
ユーザー |
|
提出日時 | 2024-10-25 21:38:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 358 ms / 4,000 ms |
コード長 | 1,259 bytes |
コンパイル時間 | 5,485 ms |
コンパイル使用メモリ | 313,968 KB |
実行使用メモリ | 56,704 KB |
最終ジャッジ日時 | 2024-10-25 21:38:53 |
合計ジャッジ時間 | 10,312 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; int main() { int n,m,k; cin>>n>>m>>k; vector<int> x(k); for(int i=0;i<k;i++)cin>>x[i],x[i]--; vector<vector<int>> graph(n,vector<int>(n)); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; graph[u][v]=1; graph[v][u]=1; } vector<vector<vector<int>>> dp(n,vector<vector<int>>(1<<n,vector<int>(n,-1))),mem(n,vector<vector<int>>(n,vector<int>(n))); auto rec=[&](auto rec,int v,int u,int s)->void{ if(dp[v][s][u]!=-1)return; else dp[v][s][u]=0; int cnt=0; for(int i=0;i<n;i++)if(s>>i&1)cnt++; mem[v][u][cnt-1]=1; for(int i=0;i<n;i++){ if(graph[u][i]&&(s>>i&1)==0){ rec(rec,v,i,s|(1<<i)); } } return; }; for(int i=0;i<n;i++){ rec(rec,i,i,1<<i); } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ bool ok=true; for(int ii=0;ii<k;ii++)if(mem[x[ii]][i][j]==0)ok=false; if(ok){ cout<<"Yes"<<endl; return 0; } } } cout<<"No"<<endl; return 0; }