답안 #532 :: oj.uz

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

#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	22448 KB	Output is correct
2	Correct	22448 KB	Output is correct
3	Correct	22448 KB	Output is correct
4	Correct	22448 KB	Output is correct
5	Correct	22448 KB	Output is correct
6	Correct	22448 KB	Output is correct
7	Correct	22448 KB	Output is correct
8	Correct	22448 KB	Output is correct
9	Correct	22448 KB	Output is correct
10	Correct	22448 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	메모리	Grader output
1	Correct	22448 KB	Output is correct
2	Correct	22448 KB	Output is correct
3	Correct	22448 KB	Output is correct
4	Correct	22448 KB	Output is correct
5	Correct	22448 KB	Output is correct
6	Correct	22448 KB	Output is correct
7	Correct	22448 KB	Output is correct
8	Correct	22448 KB	Output is correct
9	Correct	22448 KB	Output is correct
10	Correct	22448 KB	Output is correct
11	Correct	22448 KB	Output is correct
12	Correct	22448 KB	Output is correct
13	Correct	22448 KB	Output is correct
14	Correct	22448 KB	Output is correct
15	Correct	22448 KB	Output is correct
16	Correct	22448 KB	Output is correct
17	Correct	22448 KB	Output is correct
18	Correct	22448 KB	Output is correct
19	Correct	22448 KB	Output is correct
20	Correct	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	5 ms	22448 KB	Output is correct
7	Correct	5 ms	22448 KB	Output is correct
8	Correct	3 ms	22448 KB	Output is correct
9	Correct	1 ms	22448 KB	Output is correct
10	Correct	15 ms	22448 KB	Output is correct
11	Correct	19 ms	22448 KB	Output is correct
12	Correct	7 ms	22448 KB	Output is correct
13	Correct	22 ms	22448 KB	Output is correct
14	Correct	9 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	18 ms	22448 KB	Output is correct
19	Correct	6 ms	22448 KB	Output is correct
20	Correct	5 ms	22448 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	2 ms	22448 KB	Output is correct
5	Correct	2 ms	22448 KB	Output is correct
6	Correct	83 ms	22448 KB	Output is correct
7	Correct	284 ms	22448 KB	Output is correct
8	Correct	167 ms	22448 KB	Output is correct
9	Correct	505 ms	22448 KB	Output is correct
10	Correct	469 ms	22448 KB	Output is correct
11	Correct	188 ms	22448 KB	Output is correct
12	Correct	179 ms	22448 KB	Output is correct
13	Correct	378 ms	22448 KB	Output is correct
14	Correct	288 ms	22448 KB	Output is correct
15	Correct	83 ms	22448 KB	Output is correct
16	Correct	13 ms	22448 KB	Output is correct
17	Correct	13 ms	22448 KB	Output is correct
18	Correct	161 ms	22448 KB	Output is correct
19	Correct	370 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	1 ms	22448 KB	Output is correct
3	Correct	4 ms	22448 KB	Output is correct
4	Correct	5 ms	22448 KB	Output is correct
5	Correct	99 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	-

답안 #532

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 0.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
0.0 / 35.0