https://www.acmicpc.net/problem/31840
문제 요약
- N개의 노드 M 개의 간선(30만)
- 1 부터 N까지 이동할때 간선들의 "OR" 최소값 구하기
- 간선은 2^60 미만
접근법
- 처음에는 XOR인줄 알았는데 OR 이었음
- 59번째 비트(2^59)를 사용하지 않고 1 -> N 까지 이동 가능한지 판단
- 59 번째 비트가 사용되지 않는 간선만 모아서 union-find 수행
- 1과 N이 연결되어있으면 59번째 비트 없이도 가능!
- 이후 탐색은 59번째 비트가 사용되지 않는 간선들로만 수행
- 만약에 1과 N이 연결되지 않는다면 59번째 비트는 사용해야함 -> 정답에도 반영
- 58, 57, 56 .... 0번째 비트까지 모두 판단
newbieski