답안 #521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521 2013-02-28T08:02:13 Z tncks0121 지도 색칠하기 (GA3_map) C++
120 / 120
997 ms 920 KB
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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Correct 0 ms 920 KB Output is correct
7 Correct 0 ms 920 KB Output is correct
8 Correct 0 ms 920 KB Output is correct
9 Correct 0 ms 920 KB Output is correct
10 Correct 0 ms 920 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 0 ms 920 KB Output is correct
6 Correct 0 ms 920 KB Output is correct
7 Correct 0 ms 920 KB Output is correct
8 Correct 0 ms 920 KB Output is correct
9 Correct 0 ms 920 KB Output is correct
10 Correct 0 ms 920 KB Output is correct
11 Correct 0 ms 920 KB Output is correct
12 Correct 0 ms 920 KB Output is correct
13 Correct 0 ms 920 KB Output is correct
14 Correct 0 ms 920 KB Output is correct
15 Correct 0 ms 920 KB Output is correct
16 Correct 0 ms 920 KB Output is correct
17 Correct 0 ms 920 KB Output is correct
18 Correct 0 ms 920 KB Output is correct
19 Correct 0 ms 920 KB Output is correct
20 Correct 0 ms 920 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 920 KB Output is correct
2 Correct 0 ms 920 KB Output is correct
3 Correct 0 ms 920 KB Output is correct
4 Correct 0 ms 920 KB Output is correct
5 Correct 2 ms 920 KB Output is correct
6 Correct 3 ms 920 KB Output is correct
7 Correct 1 ms 920 KB Output is correct
8 Correct 1 ms 920 KB Output is correct
9 Correct 1 ms 920 KB Output is correct
10 Correct 3 ms 920 KB Output is correct
11 Correct 2 ms 920 KB Output is correct
12 Correct 0 ms 920 KB Output is correct
13 Correct 2 ms 920 KB Output is correct
14 Correct 1 ms 920 KB Output is correct
15 Correct 2 ms 920 KB Output is correct
16 Correct 8 ms 920 KB Output is correct
17 Correct 3 ms 920 KB Output is correct
18 Correct 4 ms 920 KB Output is correct
19 Correct 0 ms 920 KB Output is correct
20 Correct 1 ms 920 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 920 KB Output is correct
2 Correct 19 ms 920 KB Output is correct
3 Correct 9 ms 920 KB Output is correct
4 Correct 13 ms 920 KB Output is correct
5 Correct 21 ms 920 KB Output is correct
6 Correct 14 ms 920 KB Output is correct
7 Correct 33 ms 920 KB Output is correct
8 Correct 14 ms 920 KB Output is correct
9 Correct 24 ms 920 KB Output is correct
10 Correct 28 ms 920 KB Output is correct
11 Correct 12 ms 920 KB Output is correct
12 Correct 14 ms 920 KB Output is correct
13 Correct 22 ms 920 KB Output is correct
14 Correct 20 ms 920 KB Output is correct
15 Correct 10 ms 920 KB Output is correct
16 Correct 96 ms 920 KB Output is correct
17 Correct 87 ms 920 KB Output is correct
18 Correct 15 ms 920 KB Output is correct
19 Correct 21 ms 920 KB Output is correct
20 Correct 11 ms 920 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 920 KB Output is correct
2 Correct 92 ms 920 KB Output is correct
3 Correct 92 ms 920 KB Output is correct
4 Correct 92 ms 920 KB Output is correct
5 Correct 123 ms 920 KB Output is correct
6 Correct 140 ms 920 KB Output is correct
7 Correct 124 ms 920 KB Output is correct
8 Correct 111 ms 920 KB Output is correct
9 Correct 131 ms 920 KB Output is correct
10 Correct 128 ms 920 KB Output is correct
11 Correct 106 ms 920 KB Output is correct
12 Correct 104 ms 920 KB Output is correct
13 Correct 107 ms 920 KB Output is correct
14 Correct 99 ms 920 KB Output is correct
15 Correct 95 ms 920 KB Output is correct
16 Correct 415 ms 920 KB Output is correct
17 Correct 423 ms 920 KB Output is correct
18 Correct 120 ms 920 KB Output is correct
19 Correct 89 ms 920 KB Output is correct
20 Correct 107 ms 920 KB Output is correct
21 Correct 997 ms 920 KB Output is correct
22 Correct 976 ms 920 KB Output is correct
23 Correct 261 ms 920 KB Output is correct
24 Correct 169 ms 920 KB Output is correct
25 Correct 182 ms 920 KB Output is correct
26 Correct 242 ms 920 KB Output is correct
27 Correct 258 ms 920 KB Output is correct
28 Correct 269 ms 920 KB Output is correct
29 Correct 238 ms 920 KB Output is correct
30 Correct 247 ms 920 KB Output is correct