結果
問題 | No.2948 move move rotti |
ユーザー |
![]() |
提出日時 | 2024-10-25 21:44:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 747 ms / 4,000 ms |
コード長 | 909 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 82,716 KB |
実行使用メモリ | 114,600 KB |
最終ジャッジ日時 | 2024-10-25 21:45:06 |
合計ジャッジ時間 | 7,765 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,M,K=map(int,input().split()) A=list(map(int,input().split())) p=[0]*N G=[[] for i in range(N)] v=[[0]*N for i in range(N+1)] for i in range(K): A[i]-=1 for i in range(K): p[A[i]]+=1 for i in range(M): a,b=map(int,input().split()) G[a-1].append(b-1) G[b-1].append(a-1) for x in range(N): if not x in A: continue h=[[0]*N for i in range(N+1)] dp=[0]*(N*(2**N)) dp[(2**x)*N+x]=1 v[1][x]+=p[x] for bit in range(1,2**N): count=0 for k in range(N): if (bit>>k)&1: count+=1 for i in range(N): if dp[bit*N+i]==0: continue for j in G[i]: if (bit>>j)&1: continue bit2=bit+2**j h[count+1][j]=1 dp[bit2*N+j]=1 for i in range(N+1): for j in range(N): v[i][j]+=p[x]*h[i][j] for count in range(1,N+1): for j in range(N): if v[count][j]==K: print('Yes') exit() print('No')