Submission #748

#	Time	Username	Problem	Language	Result	Execution time	Memory
748		gs12117	지도 색칠하기 (GA3_map)	C++98	0 / 120	173 ms	920 KiB

map

#include<stdio.h>
int n,m;
int edge[22][22];
int en[22];
int c[22];
int dfs(int a,int b,int graph){
	int i,j;
	c[a]=b;
	for(i=0;i<en[a];i++){
		if((graph>>edge[a][i])&1){
			if(c[edge[a][i]]==0){
				j=dfs(edge[a][i],3-b,graph);
				if(j==0)return 0;
			}
			if(c[edge[a][i]]==b)return 0;
		}
	}
	return 1;
}
long long int color(int a){
	int b,i,j,k;
	long long int r=1;
	for(i=0;i<n;i++){
		c[i]=0;
	}
	for(i=0;i<n;i++){
		if((a>>i)&1){
			if(c[i]==0){
				j=dfs(i,1,a);
				if(j==0)return 0;
				else r*=2;
			}
		}
	}
	return r;
}
long long int NumberOfMaps(int N,int M,int *A,int *B){
	int i;
	long long int ans;
	n=N;
	m=M;
	for(i=0;i<m;i++){
		A[i]--;
		B[i]--;
		edge[A[i]][en[A[i]]]=B[i];
		edge[B[i]][en[B[i]]]=A[i];
		en[A[i]]++;
		en[B[i]]++;
	}
	ans=0;
	for(i=0;i<(1<<(n));i++){
		ans+=color(i)*color((1<<n)-i-1);
	}
	ans*=2;
	return ans;
}

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