답안 #17300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17300	2015-11-19T07:38:02 Z	gs14004	지도 색칠하기 (GA3_map)	C++14	85 / 120	1500 ms	1088 KB

map

struct disj{
	int pa[42];
	void init(int n){
		for(int i=1; i<=n; i++) pa[i] = i;
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p;
		return 1;
	}
}disj;

long long NumberOfMaps (int N, int M, int *A, int *B){
	long long sum = 0;
	for(int i=0; i<(1<<(N-1)); i++){
		disj.init(2*N);
		bool bad = 0;
		for(int j=0; j<M; j++){
			if(((i >> (A[j] - 1)) & 1) == ((i >> (B[j] - 1)) & 1)){
				disj.uni(A[j], B[j] + N);
				disj.uni(B[j], A[j] + N);
				if(disj.find(A[j]) == disj.find(A[j] + N)){
					bad = 1;
					break;
				}
			}
		}
		if(bad) continue;
		int cnt = 0;
		for(int i=1; i<=2*N; i++){
			if(disj.uni(i, 1)){
				cnt++;
			}
		}
		cnt = (cnt + 1) / 2;
		sum += (2 << cnt);
	}
	return sum;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

25.0 / 25.0

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

Subtask #4

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1088 KB	Output is correct
2	Correct	22 ms	1088 KB	Output is correct
3	Correct	11 ms	1088 KB	Output is correct
4	Correct	18 ms	1088 KB	Output is correct
5	Correct	27 ms	1088 KB	Output is correct
6	Correct	18 ms	1088 KB	Output is correct
7	Correct	49 ms	1088 KB	Output is correct
8	Correct	15 ms	1088 KB	Output is correct
9	Correct	25 ms	1088 KB	Output is correct
10	Correct	26 ms	1088 KB	Output is correct
11	Correct	21 ms	1088 KB	Output is correct
12	Correct	17 ms	1088 KB	Output is correct
13	Correct	33 ms	1088 KB	Output is correct
14	Correct	25 ms	1088 KB	Output is correct
15	Correct	18 ms	1088 KB	Output is correct
16	Correct	147 ms	1088 KB	Output is correct
17	Correct	140 ms	1088 KB	Output is correct
18	Correct	23 ms	1088 KB	Output is correct
19	Correct	28 ms	1088 KB	Output is correct
20	Correct	10 ms	1088 KB	Output is correct

Subtask #5

0.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	1088 KB	Output is correct
2	Correct	100 ms	1088 KB	Output is correct
3	Correct	117 ms	1088 KB	Output is correct
4	Correct	126 ms	1088 KB	Output is correct
5	Correct	211 ms	1088 KB	Output is correct
6	Correct	185 ms	1088 KB	Output is correct
7	Correct	170 ms	1088 KB	Output is correct
8	Correct	136 ms	1088 KB	Output is correct
9	Correct	143 ms	1088 KB	Output is correct
10	Correct	176 ms	1088 KB	Output is correct
11	Correct	94 ms	1088 KB	Output is correct
12	Correct	118 ms	1088 KB	Output is correct
13	Correct	140 ms	1088 KB	Output is correct
14	Correct	170 ms	1088 KB	Output is correct
15	Correct	140 ms	1088 KB	Output is correct
16	Correct	656 ms	1088 KB	Output is correct
17	Correct	676 ms	1088 KB	Output is correct
18	Correct	153 ms	1088 KB	Output is correct
19	Correct	113 ms	1088 KB	Output is correct
20	Correct	150 ms	1088 KB	Output is correct
21	Execution timed out	1500 ms	1088 KB	Program timed out
22	Halted	0 ms	0 KB	-