Submission #749

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
749	2013-03-01T18:38:20 Z	gs12117	지도 색칠하기 (GA3_map)	C++	85 / 120	1500 ms	920 KB

map

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);
	}
	return ans;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	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	2 ms	920 KB	Output is correct
17	Correct	1 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

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	920 KB	Output is correct
2	Correct	2 ms	920 KB	Output is correct
3	Correct	1 ms	920 KB	Output is correct
4	Correct	2 ms	920 KB	Output is correct
5	Correct	4 ms	920 KB	Output is correct
6	Correct	6 ms	920 KB	Output is correct
7	Correct	3 ms	920 KB	Output is correct
8	Correct	3 ms	920 KB	Output is correct
9	Correct	2 ms	920 KB	Output is correct
10	Correct	7 ms	920 KB	Output is correct
11	Correct	7 ms	920 KB	Output is correct
12	Correct	2 ms	920 KB	Output is correct
13	Correct	6 ms	920 KB	Output is correct
14	Correct	4 ms	920 KB	Output is correct
15	Correct	4 ms	920 KB	Output is correct
16	Correct	16 ms	920 KB	Output is correct
17	Correct	7 ms	920 KB	Output is correct
18	Correct	6 ms	920 KB	Output is correct
19	Correct	2 ms	920 KB	Output is correct
20	Correct	3 ms	920 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	920 KB	Output is correct
2	Correct	41 ms	920 KB	Output is correct
3	Correct	19 ms	920 KB	Output is correct
4	Correct	24 ms	920 KB	Output is correct
5	Correct	44 ms	920 KB	Output is correct
6	Correct	31 ms	920 KB	Output is correct
7	Correct	69 ms	920 KB	Output is correct
8	Correct	28 ms	920 KB	Output is correct
9	Correct	49 ms	920 KB	Output is correct
10	Correct	57 ms	920 KB	Output is correct
11	Correct	26 ms	920 KB	Output is correct
12	Correct	28 ms	920 KB	Output is correct
13	Correct	43 ms	920 KB	Output is correct
14	Correct	41 ms	920 KB	Output is correct
15	Correct	23 ms	920 KB	Output is correct
16	Correct	193 ms	920 KB	Output is correct
17	Correct	176 ms	920 KB	Output is correct
18	Correct	29 ms	920 KB	Output is correct
19	Correct	45 ms	920 KB	Output is correct
20	Correct	20 ms	920 KB	Output is correct

Subtask #5

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	920 KB	Output is correct
2	Correct	180 ms	920 KB	Output is correct
3	Correct	189 ms	920 KB	Output is correct
4	Correct	186 ms	920 KB	Output is correct
5	Correct	242 ms	920 KB	Output is correct
6	Correct	282 ms	920 KB	Output is correct
7	Correct	233 ms	920 KB	Output is correct
8	Correct	227 ms	920 KB	Output is correct
9	Correct	261 ms	920 KB	Output is correct
10	Correct	247 ms	920 KB	Output is correct
11	Correct	200 ms	920 KB	Output is correct
12	Correct	205 ms	920 KB	Output is correct
13	Correct	214 ms	920 KB	Output is correct
14	Correct	192 ms	920 KB	Output is correct
15	Correct	190 ms	920 KB	Output is correct
16	Correct	823 ms	920 KB	Output is correct
17	Correct	850 ms	920 KB	Output is correct
18	Correct	248 ms	920 KB	Output is correct
19	Correct	177 ms	920 KB	Output is correct
20	Correct	221 ms	920 KB	Output is correct
21	Execution timed out	1500 ms	920 KB	Program timed out
22	Halted	0 ms	0 KB	-
23	Halted	0 ms	0 KB	-
24	Halted	0 ms	0 KB	-
25	Halted	0 ms	0 KB	-
26	Halted	0 ms	0 KB	-
27	Halted	0 ms	0 KB	-
28	Halted	0 ms	0 KB	-
29	Halted	0 ms	0 KB	-
30	Halted	0 ms	0 KB	-