답안 #535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535	2013-02-28T11:21:20 Z	kriii	지도 색칠하기 (GA3_map)	C++	55 / 120	120 ms	65536 KB

map

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

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

	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]){
		int x = (1 << N) - 1 - i;
		for (j=x;j;j=(j-1)&x){
			U[i+j].push_back(i);
		}
		U[i].push_back(i);
	}

	for (i=1;i<(1<<N);i++) if (mul[i] == 0){
		for (j=0;j<U[i].size();j++){
			x = U[i][j];
			if (go[x] & (i-x)) continue;
			if ((x) & go[i-x]) continue;
			mul[i] = mul[x] * mul[i-x];
			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	6 ms	46000 KB	Output is correct
2	Correct	3 ms	46000 KB	Output is correct
3	Correct	4 ms	46000 KB	Output is correct
4	Correct	3 ms	46000 KB	Output is correct
5	Correct	3 ms	46000 KB	Output is correct
6	Correct	4 ms	46000 KB	Output is correct
7	Correct	4 ms	46000 KB	Output is correct
8	Correct	6 ms	46000 KB	Output is correct
9	Correct	7 ms	46000 KB	Output is correct
10	Correct	2 ms	46000 KB	Output is correct

Subtask #2

20.0 / 20.0

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

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	46924 KB	Output is correct
2	Correct	8 ms	46396 KB	Output is correct
3	Correct	7 ms	46396 KB	Output is correct
4	Correct	7 ms	46528 KB	Output is correct
5	Correct	16 ms	47056 KB	Output is correct
6	Correct	17 ms	48244 KB	Output is correct
7	Correct	14 ms	47980 KB	Output is correct
8	Correct	18 ms	47848 KB	Output is correct
9	Correct	11 ms	46792 KB	Output is correct
10	Correct	33 ms	52084 KB	Output is correct
11	Correct	43 ms	54580 KB	Output is correct
12	Correct	22 ms	49036 KB	Output is correct
13	Correct	43 ms	54052 KB	Output is correct
14	Correct	23 ms	49300 KB	Output is correct
15	Correct	32 ms	49300 KB	Output is correct
16	Correct	83 ms	65412 KB	Output is correct
17	Correct	29 ms	52608 KB	Output is correct
18	Correct	57 ms	56300 KB	Output is correct
19	Correct	23 ms	49036 KB	Output is correct
20	Correct	18 ms	49432 KB	Output is correct

Subtask #4

0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	50224 KB	Output is correct
2	Correct	77 ms	55240 KB	Output is correct
3	Correct	36 ms	50488 KB	Output is correct
4	Correct	53 ms	52468 KB	Output is correct
5	Correct	89 ms	56428 KB	Output is correct
6	Memory limit exceeded	108 ms	65536 KB	Memory limit exceeded
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	-

Subtask #5

0.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Memory limit exceeded	120 ms	65536 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-
3	Halted	0 ms	0 KB	-
4	Halted	0 ms	0 KB	-
5	Halted	0 ms	0 KB	-
6	Halted	0 ms	0 KB	-
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	-