Submission #17301

# Submission time Handle Problem Language Result Execution time Memory
17301 2015-11-19T11:12:53 Z gs14004 지도 색칠하기 (GA3_map) C++14
85 / 120
1500 ms 1088 KB
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;
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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 1 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
# Verdict Execution time Memory 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 0 ms 1088 KB Output is correct
6 Correct 5 ms 1088 KB Output is correct
7 Correct 0 ms 1088 KB Output is correct
8 Correct 2 ms 1088 KB Output is correct
9 Correct 2 ms 1088 KB Output is correct
10 Correct 4 ms 1088 KB Output is correct
11 Correct 4 ms 1088 KB Output is correct
12 Correct 0 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 4 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 4 ms 1088 KB Output is correct
19 Correct 2 ms 1088 KB Output is correct
20 Correct 3 ms 1088 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 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 19 ms 1088 KB Output is correct
5 Correct 28 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 18 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 19 ms 1088 KB Output is correct
16 Correct 147 ms 1088 KB Output is correct
17 Correct 141 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
# Verdict Execution time Memory Grader output
1 Correct 93 ms 1088 KB Output is correct
2 Correct 101 ms 1088 KB Output is correct
3 Correct 118 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 186 ms 1088 KB Output is correct
7 Correct 171 ms 1088 KB Output is correct
8 Correct 137 ms 1088 KB Output is correct
9 Correct 142 ms 1088 KB Output is correct
10 Correct 175 ms 1088 KB Output is correct
11 Correct 94 ms 1088 KB Output is correct
12 Correct 119 ms 1088 KB Output is correct
13 Correct 141 ms 1088 KB Output is correct
14 Correct 169 ms 1088 KB Output is correct
15 Correct 143 ms 1088 KB Output is correct
16 Correct 657 ms 1088 KB Output is correct
17 Correct 677 ms 1088 KB Output is correct
18 Correct 152 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 -