Submission #490

#	Time	Username	Problem	Language	Result	Execution time	Memory
490		tncks0121	지도 색칠하기 (GA3_map)	C++98	120 / 120	1006 ms	920 KiB

map

typedef long long ll;

#include<stdio.h>
int n,m;
int edge[25][25];
int en[25];
int c[25];
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 NumberOfMaps (int N, int M, int *A, int *B){
	int i,a,b;
	long long int ans;
	n=N; m=M;
	for(i=0;i<m;i++){
		a=A[i]; b=B[i];
		a--;
		b--;
		edge[a][en[a]]=b;
		edge[b][en[b]]=a;
		en[a]++;
		en[b]++;
	}
	ans=0;
	for(i=0;i<(1<<(n-1));i++){
		ans+=color(i)*color((1<<n)-i-1);
	}
	ans*=2;
	return ans;
}

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