20557번 - 복잡한 쿼리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 58 | 40 | 32 | 66.667% |
문제
출제진은 여러분들이 고통받는 모습을 즐기기에 여러분들이 그다지 보고 싶지 않은 주제들을 합쳐서 문제를 내기로 했다. NP 문제인 최장 경로 문제, XOR, 쿼리가 합쳐진 이 문제를 풀어보자!
$N$개의 정점과 $M$개의 가중치 있는 무방향 간선들로 이루어진 연결그래프 $G$가 있다. $G$에서 경로의 가중치는 일반적인 경우와 다르게 계산되는데, 지난 간선들의 가중치들을 XOR한 값이다. 한 간선을 여러 번 지나는 것이 허용되며, 이 경우 그 횟수만큼 XOR해야 함에 유의하자.
정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 최대 가중치의 경로를 $u$에서 $v$로 가는 최장 경로라고 한다. 이 때, 최장 경로의 가중치를 $d(u,v)$라고 하자. $Q$번 다음과 같은 쿼리를 해결해야 한다.
- $l$ $r$: $l \leq i < j \leq r $인 모든 $i$와 $j$에 대해, $d(i,j)$ 값들을 XOR한 값을 구한다.
입력
첫 번째 줄에 $N$, $M$, $Q$가 주어진다. $(1 \leq N,M,Q \leq 100\,000)$
이후 $M$개의 줄에 걸쳐 간선의 정보가 $u$, $v$, $w$가 주어진다. 이는 정점 $u$와 $v$를 잇는 가중치 $w$의 간선이라는 뜻이다. 양 끝점이 같은 간선이 있을 수 있으며 같은 정점 쌍을 잇는 간선이 여럿 있을 수 있음에 유의하라. $(1 \leq u,v \leq N, 0 \leq w < 2^{30})$
이후 $Q$개의 줄에 걸쳐 쿼리의 정보 $l$, $r$이 주어진다. $(1 \leq l < r \leq N)$
출력
각 쿼리의 답을 순서대로 줄바꿈으로 구분하여 출력한다.
예제 입력 1
8 10 7 1 2 662784558 3 2 195868257 3 4 294212653 4 5 299265014 6 5 72652580 6 7 29303370 7 8 183954825 2 1 752722885 5 3 197591314 8 4 877461873 4 8 5 7 6 7 2 3 7 8 3 4 2 7
예제 출력 1
0 713437792 738051848 716356296 736682272 1003204975 987493236
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호