| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 534 | 2013-02-28T11:20:16 Z | kriii | 쉬운 문제 (GA3_easy) | C++ | 0 ms | 0 KB |
#include <queue>
#include <vector>
using namespace std;
vector<int> U[1<<20];
int S[2][1<<20],con[20],go[1<<20]; long long mul[1<<20];
long long pos(int v)
{
int c = -1;
while (v){
v /= 2;
c++;
}
return c;
}
long long NumberOfMaps (int N, int M, int *A, int *B)
{
long long ret = 0;
int i,j,u,x;
for (i=0;i<M;i++){
A[i]--; B[i]--;
con[A[i]] |= 1 << B[i];
con[B[i]] |= 1 << A[i];
}
for (i=1;i<(1<<N);i++){
if (i == (i & (-i))) go[i] = con[pos(i)];
else{
x = i & (-i);
go[i] = go[x] | go[i-x];
}
}
mul[0] = 1;
queue<int> Q;
for (i=0;i<N;i++){
Q.push(1<<i); S[0][1<<i] = 1<<i; mul[1<<i] = 2;
}
while (!Q.empty()){
x = Q.front(); Q.pop();
int can = go[x] & (~x);
while (can){
int now = (can & (-can));
u = x + (can & (-can));
can -= can & (-can);
if ((S[0][x] & go[now]) && (S[1][x] & go[now])) continue;
if (mul[u] == 0){
Q.push(u); mul[u] = 2;
S[0][u] = S[0][x];
S[1][u] = S[1][x];
if ((S[1][x] & go[now])) S[0][u] |= now;
else S[1][u] |= now;
}
}
}
for (i=1;i<(1<<N);i++) if (mul[i]){
int x = (1 << N) - 1 - i;
for (j=x;j;j=(j-1)&x){
U[i+j].push_back(i);
}
U[i].push_back(i);
}
for (i=1;i<(1<<N);i++) if (mul[i] == 0){
for (j=0;j<U[i].size();j++){
x = U[i][j];
if (go[x] & (i-x)) continue;
if ((x) & go[i-x]) continue;
mul[i] = mul[x] * mul[i-x];
break;
}
}
for (i=0;i<(1<<N);i++){
j = (1<<N)-1 - i;
ret += mul[i] * mul[j];
}
return ret;
}