Submission #536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
536	2013-02-28T11:33:29 Z	kriii	지도 색칠하기 (GA3_map)	C++	120 / 120	1222 ms	22212 KB

#include <queue>
#include <vector>
using namespace std;

vector<int> U;
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];
		}
	}

	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=0;i<(1<<N);i++) if (mul[i] == 0){
		Q.push(i&(-i)); int chk = i&(-i);
		while (!Q.empty()){
			x = Q.front(); Q.pop();
			int can = go[x];
			while (can){
				int now = (can & (-can));
				if ((i & now) && (chk & now) == 0){
					Q.push(now); chk |= now;
				}
				can -= now;
			}
		}
		if (mul[chk] && mul[i-chk]){
			mul[i] = mul[chk] * mul[i-chk];
		}
	}

	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

#	Verdict	Memory	Grader output
1	Correct	21424 KB	Output is correct
2	Correct	21424 KB	Output is correct
3	Correct	21424 KB	Output is correct
4	Correct	21424 KB	Output is correct
5	Correct	21424 KB	Output is correct
6	Correct	21424 KB	Output is correct
7	Correct	21424 KB	Output is correct
8	Correct	21424 KB	Output is correct
9	Correct	21424 KB	Output is correct
10	Correct	21424 KB	Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	21424 KB	Output is correct
2	Correct	1 ms	21424 KB	Output is correct
3	Correct	0 ms	21424 KB	Output is correct
4	Correct	1 ms	21424 KB	Output is correct
5	Correct	3 ms	21424 KB	Output is correct
6	Correct	9 ms	21424 KB	Output is correct
7	Correct	18 ms	21424 KB	Output is correct
8	Correct	20 ms	21424 KB	Output is correct
9	Correct	43 ms	21424 KB	Output is correct
10	Correct	34 ms	21424 KB	Output is correct
11	Correct	26 ms	21424 KB	Output is correct
12	Correct	31 ms	21424 KB	Output is correct
13	Correct	100 ms	21424 KB	Output is correct
14	Correct	131 ms	21424 KB	Output is correct
15	Correct	62 ms	21424 KB	Output is correct
16	Correct	12 ms	21424 KB	Output is correct
17	Correct	15 ms	21424 KB	Output is correct
18	Correct	40 ms	21424 KB	Output is correct
19	Correct	114 ms	21424 KB	Output is correct
20	Correct	47 ms	21424 KB	Output is correct

Subtask #5
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	21424 KB	Output is correct
2	Correct	5 ms	21424 KB	Output is correct
3	Correct	5 ms	21424 KB	Output is correct
4	Correct	8 ms	21424 KB	Output is correct
5	Correct	17 ms	21424 KB	Output is correct
6	Correct	122 ms	21424 KB	Output is correct
7	Correct	39 ms	21424 KB	Output is correct
8	Correct	127 ms	21424 KB	Output is correct
9	Correct	233 ms	21424 KB	Output is correct
10	Correct	48 ms	21424 KB	Output is correct
11	Correct	628 ms	21424 KB	Output is correct
12	Correct	499 ms	21424 KB	Output is correct
13	Correct	294 ms	21424 KB	Output is correct
14	Correct	641 ms	21424 KB	Output is correct
15	Correct	661 ms	21424 KB	Output is correct
16	Correct	106 ms	21816 KB	Output is correct
17	Correct	99 ms	21816 KB	Output is correct
18	Correct	444 ms	21424 KB	Output is correct
19	Correct	559 ms	21424 KB	Output is correct
20	Correct	472 ms	21424 KB	Output is correct
21	Correct	276 ms	22212 KB	Output is correct
22	Correct	278 ms	22212 KB	Output is correct
23	Correct	1008 ms	21424 KB	Output is correct
24	Correct	1222 ms	21424 KB	Output is correct
25	Correct	1204 ms	21424 KB	Output is correct
26	Correct	33 ms	21424 KB	Output is correct
27	Correct	60 ms	21424 KB	Output is correct
28	Correct	134 ms	21816 KB	Output is correct
29	Correct	38 ms	21424 KB	Output is correct
30	Correct	46 ms	21424 KB	Output is correct

Submission #536

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 25.0 / 25.0

Subtask #4 30.0 / 30.0

Subtask #5 35.0 / 35.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
25.0 / 25.0

Subtask #4
30.0 / 30.0

Subtask #5
35.0 / 35.0