Submission #3782184
Source Code Expand
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <unordered_map> using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=1e9+7; int par[21]; int rk[21]; void init(int n){ for(int i=0; i<n; i++){ par[i]=i; rk[i]=0; } } int find(int x){ if(par[x]==x){ return x; }else{ return par[x]=find(par[x]); } } void unite(int x, int y){ x=find(x); y=find(y); if(x==y) return; if(rk[x]<rk[y]){ par[x]=y; }else{ par[y]=x; if(rk[x]==rk[y]) rk[x]++; } } bool same(int x, int y){ return find(x)==find(y); } int main() { int h, w; cin>>h>>w; unordered_map<string, ll> dp[2]; for(int i=1; i<(1<<h); i+=2){ init(h); for(int j=1; j<h; j++){ if((i&(1<<(j-1))) && (i&(1<<j))){ unite(j-1, j); } } int p[6], c=1; fill(p, p+h, -1); string s; for(int j=0; j<h; j++){ if(i&(1<<j)){ if(p[find(j)]==-1){ p[find(j)]=c; c++; } s+=('0'+p[find(j)]); }else{ s+='0'; } } dp[0][s]=1; } for(int l=1; l<w; l++){ for(int i=1; i<(1<<h); i++){ for(auto p:dp[(l-1)&1]){ string t=p.first; init(3*h); for(int k=0; k<h; k++){ if(t[k]>'0'){ unite(t[k]-'0', k+h); if(i&(1<<k)){ unite(k+h, k+2*h); } } } for(int k=1; k<h; k++){ if(t[k]>'0' && t[k-1]>'0'){ unite(k-1+h, k+h); } if((i&(1<<(k-1))) && (i&(1<<k))){ unite(k-1+2*h, k+2*h); } } int q[18]; fill(q, q+3*h, -1); int c=2; q[find(1)]=1; string s; bool ok=0; for(int k=0; k<h; k++){ if(i&(1<<k)){ if(q[find(k+2*h)]==-1){ q[find(k+2*h)]=c; c++; }else if(q[find(k+2*h)]==1){ ok=1; } s+=('0'+q[find(k+2*h)]); }else{ s+='0'; } } if(!ok) continue; dp[l&1][s]+=p.second; dp[l&1][s]%=MOD; } } dp[(l-1)&1].clear(); } ll ans=0; for(auto p:dp[(w-1)&1]){ string t=p.first; if(t[h-1]=='1'){ ans=(ans+p.second)%MOD; } } cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | S - マス目 |
User | chocorusk |
Language | C++14 (GCC 5.4.1) |
Score | 7 |
Code Size | 2572 Byte |
Status | AC |
Exec Time | 576 ms |
Memory | 256 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 7 / 7 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 559 ms | 256 KB |
01 | AC | 576 ms | 256 KB |
02 | AC | 30 ms | 256 KB |
03 | AC | 12 ms | 256 KB |
04 | AC | 2 ms | 256 KB |
05 | AC | 2 ms | 256 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 8 ms | 256 KB |