21973번 - 남극 탐험 다국어인터랙티브
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 30 초 | 512 MB | 240 | 57 | 44 | 24.309% |
문제
상근이는 "얼음을 꿈꾸다" 여행사의 사장이다. 이 여행사는 남극 근처의 섬 N개를 구매해 당일치기 여행을 제공하고 있다. 관광객들에게 가장 인기 있는 동물은 황제 펭귄으로 섬에서 쉽게 찾을 수 있다.
여행사는 점점 인기를 얻게 되었고, 이제 보트를 이용하는 것이 효율적이지 않은 상황까지 이르렀다. 상근이는 섬 사이에 다리를 건설해 관광객을 버스로 이동시키려고 한다. 상근이는 컴퓨터 프로그램을 이용해서 다리를 건설하는 과정을 관리하려고 한다.
섬은 1번부터 N번까지 번호가 매겨져 있다. 가장 처음에는 아무 다리도 없으며, 각 섬에 펭귄이 몇 마리 살고있는지는 모두 알고있다. 펭귄의 수는 변할 수 있다. 하지만, 항상 0보다 크거나 같고, 1000보다 작거나 같다.
상근이의 프로그램은 다음과 같은 세 가지 명령을 수행할 수 있어야 한다.
- "bridge A B" - 섬 A와 B사이에 다리를 건설하는 명령이다. (A와 B는 다르다) 이전까지 지어진 다리를 이용해서 이동할 수 없는 경우에만 다리를 지어야 한다. 다리를 지어야 하면 "yes", 지을 필요가 없이 이미 이동할 수 있으면 "no"를 출력한다.
- "penguins A X" - 섬 A에 살고있는 펭귄의 수를 다시 세보니 X마리가 되었다는 명령이다. 아무것도 출력할 필요가 없다.
- "excursion A B" - 관광객들이 섬 A에서 시작해 B에서 끝나는 여행 경로를 이용하는 명령이다. A에서 B로 갈 수 있는 경우에는 이동하는 섬에 있는 모든 펭귄의 수를 구해 출력한다. (A와 B 포함) 이동할 수 없는 경우에는 "impossible"를 출력한다.
상근이의 프로그램을 작성하시오.
"bridge", "excursion" 명령에 대한 답을 출력하기 전에는 이후 명령이 주어지지 않는다. 따라서, 출력한 후에는 표준 출력 버퍼를 flush 해주어야 한다.
입력
첫째 줄에 섬의 수 N (1 ≤ N ≤ 30,000)이 주어진다.
둘째 줄에는 각 섬에 있는 펭귄의 수가 주어진다.
셋째 줄에는 명령의 개수 Q (1 ≤ Q ≤ 300,000)가 주어진다.
다음 Q개 줄에는 문제에서 주어진 명령 중 하나가 주어진다.
출력
"bridge"나 "excursion" 명령이 주어질 때 마다 출력한다.
예제 입력 1
5 4 2 4 5 6 10 excursion 1 1 excursion 1 2 bridge 1 2 excursion 1 2 bridge 3 4 bridge 3 5 excursion 4 5 bridge 1 3 excursion 2 4 excursion 2 5
예제 출력 1
4 impossible yes 6 yes yes 15 yes 15 16
예제 입력 2
6 1 2 3 4 5 6 10 bridge 1 2 bridge 2 3 bridge 4 5 excursion 1 3 excursion 1 5 bridge 3 4 excursion 1 5 penguins 3 10 excursion 1 3 bridge 1 5
예제 출력 2
yes yes yes 6 impossible yes 15 13 no
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Croatian Olympiad in Informatics 2009 2번
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호