| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 17301 |
2015-11-19T11:12:53 Z |
gs14004 |
지도 색칠하기 (GA3_map) |
C++14 |
|
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 |
- |
