https://www.acmicpc.net/problem/16901
- 크루스칼, 프림 방식은 시간초과
- xor 특성 : 서로 비트가 다르면 1, 같으면 0
- 최상위 비트가 같은 것끼리 알아서 트리를 구성한다고 치고
- 두 그룹을 연결하는데 가장 적은 비용을 찾는다. : merge() 함수
- 최상위 비트가 0 : A그룹, 1 : B 그룹
- 최상위 비트는 일단 다를테니 그 다음 비트부터 살펴봄
- A 그룹중에서 두번째 비트가 0인 그룹 A0, 1인 그룹 A1
- B 그룹중에서 두번째 비트가 0인 그룹 B0, 1인 그룹 B1
- (A0, B0) 에 대해서 비용을 찾고, (A1, B1)에 대해서 비용을 찾는다.
- 이때 두 쪽 모두가 A,B로 섞이지 않았으면(A0, B1만 있거나, A1, B0만 있으면) 이번 비트로는 합쳐질 수 없음, 다음 비트부터 연산
- 한쪽이라도 섞여있으면 계속 계산해보는데, 안섞인 쪽은 적당히 최대값을 리턴하게 함
- 재귀 작업을 할때 vector를 파라미터로 넘겨주면 시간이 오래 걸리니 레퍼런스로 넘겨주거나 전역변수 사용
- 최종 노드에서 합쳐질때 union 작업 수행
newbieski