답안 #533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533	2013-02-28T11:10:58 Z	tncks0121	지도 색칠하기 (GA3_map)	C++	85 / 120	1500 ms	22448 KB

map

#include <queue>
using namespace std;

bool P[1<<20];
int S[2][1<<20],con[20],go[1<<20]; long long mul[1<<20];

long long pos(int v)
{
	int c = -1;
	while (v){
		v /= 2;
		c++;
	}
	return c;
}

long long NumberOfMaps (int N, int M, int *A, int *B)
{
	long long ret = 0;

	int i,j,u,x;

	for (i=0;i<M;i++){
		A[i]--; B[i]--;
		con[A[i]] |= 1 << B[i];
		con[B[i]] |= 1 << A[i];
	}
	for (i=1;i<(1<<N);i++){
		if (i == (i & (-i))) go[i] = con[pos(i)];
		else{
			x = i & (-i);
			go[i] = go[x] | go[i-x];
		}
	}

	P[0] = 1; mul[0] = 1;
	queue<int> Q;
	for (i=0;i<N;i++){
		Q.push(1<<i); S[0][1<<i] = 1<<i; mul[1<<i] = 2;
	}
	while (!Q.empty()){
		x = Q.front(); Q.pop();
		int can = go[x] & (~x);
		while (can){
			int now = (can & (-can));
			u = x + (can & (-can));
			can -= can & (-can);
			if ((S[0][x] & go[now]) && (S[1][x] & go[now])) continue;
			if (mul[u] == 0){
				Q.push(u); mul[u] = 2;
				S[0][u] = S[0][x];
				S[1][u] = S[1][x];
				if ((S[1][x] & go[now])) S[0][u] |= now;
				else S[1][u] |= now;
			}
		}
	}

	for (i=1;i<(1<<N);i++) if (mul[i] == 0){
		for (j=(i-1)&i;j>0;j=(j-1)&i){
			if (mul[j] && mul[i-j]){
				if (go[j] & (i-j)) continue;
				if ((j) & go[i-j]) continue;
				mul[i] = mul[j] * mul[i-j];
				P[i] = 1; break;
			}
		}
	}

	for (i=0;i<(1<<N);i++){
		j = (1<<N)-1 -i;
		ret += mul[i] * mul[j];
	}

	return ret;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	22448 KB	Output is correct
2	Correct	0 ms	22448 KB	Output is correct
3	Correct	0 ms	22448 KB	Output is correct
4	Correct	0 ms	22448 KB	Output is correct
5	Correct	0 ms	22448 KB	Output is correct
6	Correct	0 ms	22448 KB	Output is correct
7	Correct	0 ms	22448 KB	Output is correct
8	Correct	0 ms	22448 KB	Output is correct
9	Correct	0 ms	22448 KB	Output is correct
10	Correct	0 ms	22448 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	22448 KB	Output is correct
2	Correct	0 ms	22448 KB	Output is correct
3	Correct	0 ms	22448 KB	Output is correct
4	Correct	0 ms	22448 KB	Output is correct
5	Correct	0 ms	22448 KB	Output is correct
6	Correct	0 ms	22448 KB	Output is correct
7	Correct	0 ms	22448 KB	Output is correct
8	Correct	0 ms	22448 KB	Output is correct
9	Correct	0 ms	22448 KB	Output is correct
10	Correct	0 ms	22448 KB	Output is correct
11	Correct	0 ms	22448 KB	Output is correct
12	Correct	0 ms	22448 KB	Output is correct
13	Correct	0 ms	22448 KB	Output is correct
14	Correct	0 ms	22448 KB	Output is correct
15	Correct	0 ms	22448 KB	Output is correct
16	Correct	0 ms	22448 KB	Output is correct
17	Correct	0 ms	22448 KB	Output is correct
18	Correct	0 ms	22448 KB	Output is correct
19	Correct	0 ms	22448 KB	Output is correct
20	Correct	0 ms	22448 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	22448 KB	Output is correct
2	Correct	0 ms	22448 KB	Output is correct
3	Correct	0 ms	22448 KB	Output is correct
4	Correct	0 ms	22448 KB	Output is correct
5	Correct	0 ms	22448 KB	Output is correct
6	Correct	6 ms	22448 KB	Output is correct
7	Correct	5 ms	22448 KB	Output is correct
8	Correct	4 ms	22448 KB	Output is correct
9	Correct	1 ms	22448 KB	Output is correct
10	Correct	13 ms	22448 KB	Output is correct
11	Correct	18 ms	22448 KB	Output is correct
12	Correct	7 ms	22448 KB	Output is correct
13	Correct	21 ms	22448 KB	Output is correct
14	Correct	8 ms	22448 KB	Output is correct
15	Correct	9 ms	22448 KB	Output is correct
16	Correct	0 ms	22448 KB	Output is correct
17	Correct	0 ms	22448 KB	Output is correct
18	Correct	19 ms	22448 KB	Output is correct
19	Correct	7 ms	22448 KB	Output is correct
20	Correct	4 ms	22448 KB	Output is correct

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	22448 KB	Output is correct
2	Correct	0 ms	22448 KB	Output is correct
3	Correct	0 ms	22448 KB	Output is correct
4	Correct	1 ms	22448 KB	Output is correct
5	Correct	1 ms	22448 KB	Output is correct
6	Correct	89 ms	22448 KB	Output is correct
7	Correct	279 ms	22448 KB	Output is correct
8	Correct	167 ms	22448 KB	Output is correct
9	Correct	486 ms	22448 KB	Output is correct
10	Correct	463 ms	22448 KB	Output is correct
11	Correct	184 ms	22448 KB	Output is correct
12	Correct	179 ms	22448 KB	Output is correct
13	Correct	379 ms	22448 KB	Output is correct
14	Correct	285 ms	22448 KB	Output is correct
15	Correct	82 ms	22448 KB	Output is correct
16	Correct	14 ms	22448 KB	Output is correct
17	Correct	14 ms	22448 KB	Output is correct
18	Correct	158 ms	22448 KB	Output is correct
19	Correct	360 ms	22448 KB	Output is correct
20	Correct	124 ms	22448 KB	Output is correct

Subtask #5

0.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	22448 KB	Output is correct
2	Correct	4 ms	22448 KB	Output is correct
3	Correct	3 ms	22448 KB	Output is correct
4	Correct	4 ms	22448 KB	Output is correct
5	Correct	102 ms	22448 KB	Output is correct
6	Execution timed out	1500 ms	0 KB	Program timed out
7	Halted	0 ms	0 KB	-
8	Halted	0 ms	0 KB	-
9	Halted	0 ms	0 KB	-
10	Halted	0 ms	0 KB	-
11	Halted	0 ms	0 KB	-
12	Halted	0 ms	0 KB	-
13	Halted	0 ms	0 KB	-
14	Halted	0 ms	0 KB	-
15	Halted	0 ms	0 KB	-
16	Halted	0 ms	0 KB	-
17	Halted	0 ms	0 KB	-
18	Halted	0 ms	0 KB	-
19	Halted	0 ms	0 KB	-
20	Halted	0 ms	0 KB	-
21	Halted	0 ms	0 KB	-
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	-