18770번 - 불안정한 물질 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.2 초 | 256 MB | 62 | 22 | 19 | 35.185% |
문제
과학자 X는 최근 여러 종류의 초나노 스케일 물질을 합성하는데 성공했다. 합성한 물질은 총 n개이고, 각 물질은 1부터 n까지 번호를 매겼다. 물질 i의 중량은 wi 이고 각 물질은 하나씩만 존재한다.
곧 열리는 세계적인 학회인 "불안정한 물질 박람회"에 이 물질 중 일부를 특수 용기에 담아 가져가려고 하는데, 불안정한 물질이라 한 가지 제약이 있다. 각 물질 i는 특정한 다른 물질과 함께 특수 용기에 담기게 될 경우 불안정한 특성으로 인해 폭발한다. 다행히 과학자 X는 여러 번의 실험 끝에 각 물질 i는 하나의 다른 물질 Qi에만 이런식으로 반응한다는 사실을 알게 되었다.
이 정보가 주어졌을 때, 과학자 X는 폭발을 일으키지 않는 물질들의 조합을 골라서 특수 용기에 담아 가려고 한다.
예를 들어, 총 3개의 물질을 합성했고, 각 물질의 중량이 w1 = 3, w2 = 5, w3 = 1 이라 하자. 각 물질과 반응이 일어나는 다른 물질의 번호는 Q1 = 2, Q2 = 1, Q3 = 2라고 하자.
즉, 1번 물질은 2번 물질과 함께 있을 경우 반응하여 폭발하고, 2번도 1번 물질과 함께 있으면 불안정해지며 폭발한다. 마지막으로, 3번 물질은 2번 물질과 함께 있으면 폭발한다.
이 경우 1, 3번 물질은 함께 두어도 안전하고, 중량의 총합은 4이다. 하지만, 2번 물질 하나만 가져가는 경우 중량 총합이 5이므로 2번 물질만 가져가는 것이 최적의 방법이다.
과학자 X는 폭발을 일으키지 않는 물질의 조합 중에서 중량의 최대를 구하려고 한다. 이를 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 물질의 종류 수 n이 주어진다. 다음 n개의 줄에는 wi와 Qi가 한 줄에 하나씩 1번 물질부터 순서대로 주어진다.
출력
각 테스트 케이스마다 과학자 X가 가져갈 수 있는 불안정한 물질의 조합 중에서 중량의 최댓값을 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 100,000
- 1 ≤ wi ≤ 1,000,000
- 1 ≤ Qi ≤ n
- Qi ≠ i
서브태스크 1 (6점)
- 1 ≤ n ≤ 1,000
서브태스크 2 (21점)
- 1 ≤ n ≤ 100,000
예제 입력 1
4 3 3 2 5 1 1 2 3 3 2 2 3 2 1 4 1 3 2 3 3 4 4 2 4 2 2 3 1 4 4 3 3
예제 출력 1
5 3 5 7
- 테스트 케이스 1: 물질 2만 가져간다.
- 테스트 케이스 2: 물질 1만 가져간다.
- 테스트 케이스 3: 물질 1과 물질 4를 가져간다.
- 테스트 케이스 4: 물질 2와 물질 3을 가져간다.
힌트
중량의 합이 231-1을 넘을 수 있다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호