2105번 - 꼬리달린 박성원숭이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 141 | 41 | 37 | 28.462% |
문제
양 손을 사용할 수 있는 박성원숭이 N마리가 나무에 매달려 있다. 1번 박성원숭이는 꼬리로 나뭇가지에 매달려 있고 다른 박성원숭이들은 다른 박성원숭이를 손에 붙들고 있거나/고 다른 박성원숭이들의 손에 붙들려 있다(붙들리면서 붙들 수도 있음). 그런데 이 박성원숭이들은 0초부터 매 초마다 어떤 박성원숭이하나가 왼손 혹은 오른손을 놓게 된다. 그렇게 되면 의지할 곳이 없는 박성원숭이들은 ‘즉시’ 바닥으로 떨어지게 된다. 우리는 각각의 박성원숭이들이 ‘언제’ 땅에 떨어지는지 알고 싶다. 물론 떨어지지 않는 박성원숭이(이를테면 1번 박성원숭이)들도 있을 수 있다.
입력
첫 줄에 박성원숭이들의 수 N(1 ≤ N ≤ 200,000)과 박성원숭이들이 손을 놓게 되는 가짓수 M(1 ≤ M ≤ 400,000)이 주어진다. 다음 N개의 줄에 걸쳐서 각 박성원숭이의 ‘왼손’에 잡혀있는 다른 박성원숭이의 번호와(없을 경우 -1) ‘오른손’에 잡혀있는 박성원숭이의 번호(없을 경우 -1)가 각각 순서대로 주어진다. 다음 M개의 줄에 걸쳐서 손을 놓는 박성원숭이의 번호와 왼손을 놓는지 오른손을 놓는지 나타내는 숫자 1(왼손) 혹은 2(오른손)가 주어진다.
출력
각 줄에 각 박성원숭이가 언제 땅에 떨어지는지 출력한다. 떨어지지 않는다면 -1을 출력한다.
예제 입력 1
3 2 -1 3 3 -1 1 2 1 2 3 1
예제 출력 1
-1 1 1
힌트
0초에 1번 박성원숭이가 오른손을 놓지만 아직 3번이 1번을 잡고 있어서 떨어지지 않고 1초에 3번 박성원숭이가 왼손을 놓게 되면서 비로소 3번과 2번이 땅에 떨어지게 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호