Submission #5112

#	Time	Username	Problem	Language	Result	Execution time	Memory
5112		cki86201	지도 색칠하기 (GA3_map)	C++98	120 / 120	792 ms	1088 KiB

map

typedef long long ll;
 
int E[22][22], L[22], C[22], N;
 
bool dfs(int bit,int x,int now)
{
	C[x] = now;
	for(int i=0;i<L[x];i++){
		int t = E[x][i];
		if(bit&1<<t){
			if(C[t] == now)return false;
			if(C[t] == -1 && !dfs(bit,t,now^1))return false;
		}
	}
	return true;
}
 
int f(int x)
{
	int ret = 1, i;
	for(i=0;i<N;i++)C[i] = -1;
	for(i=0;i<N;i++){
		if((1<<i&x) && C[i]==-1){
			if(!dfs(x,i,0))return 0;
			ret <<= 1;
		}
	}
	return ret;
}
 
ll NumberOfMaps (int N, int M, int *A, int *B){
	::N = N;
	int i;
	for(i=0;i<M;i++){
		--A[i], --B[i];
		E[A[i]][L[A[i]]++] = B[i];
		E[B[i]][L[B[i]]++] = A[i];
	}
	ll ret = 0;
	for(i=0;i<1<<N-1;i++)ret += f(i) * f(((1<<N)-1)^i);
	return ret<<1;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35