시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 559 | 184 | 138 | 31.797% |
윤제가 사는 마을에는 $N$개의 사탕 가게가 있다. 사탕 가게는 $1$번부터 $N$번까지 번호가 매겨져 있다. 각 가게에서는 다섯 가지 종류의 사탕 중 하나만을 판매한다. 또한 사탕 가게들을 잇는 도로 $N-1$개로 이루어진 도로망이 있다. 모든 도로는 지나는 데에 $1$의 시간이 필요하며, 도로망을 이용해 한 사탕 가게에서 다른 모든 사탕 가게로 이동할 수 있다.
윤제는 오늘 $M$명의 친구를 한 명씩 순서대로 만나기로 했는데, 각 친구를 만나러 가는 길에 만날 친구가 좋아하는 종류의 사탕을 사다 주어야 한다. 이에 실패하면 친구들은 화가 나 떠나버린다.
윤제는 친구들을 빠르게 만나기 위해 한 친구를 만나고 나서 곧장 다음 친구를 만나러 출발한다. 시간을 최대한 단축하기 위해 언제나 최단 경로로 이동하며, 그 경로를 지나는 도중에 만나는 사탕 가게에 들러서 사탕을 산다. 친구가 있는 곳에 있는 가게에서 사탕을 사는 것도 가능하다. 다만, 윤제는 주머니가 작아서 사탕을 한 개만 들고 다닐 수 있다. 즉 어떤 친구 A를 만나러 가는 길에 또 다른 친구 B를 위한 사탕을 미리 사는 것은 불가능하다.
윤제는 자신을 떠날 친구들을 미리 파악하기 위해 각 친구에게 사탕을 사다 줄 수 있는지를 알고 싶어 한다. 윤제는 시작 위치를 자유롭게 선택할 수 있다. 윤제를 도와 각 친구가 좋아하는 사탕을 사다 줄 수 있는지 알려주는 프로그램을 작성하자.
첫째 줄에 사탕 가게의 개수를 나타내는 정수 $N$이 주어진다. ($1 \leq N \leq 100\ 000$)
둘째 줄에 각 사탕 가게에서 판매하는 사탕의 종류를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. 사탕의 종류는 $1$과 $5$ 사이의 양의 정수로 표현된다.
셋째 줄부터 $N-1$개의 줄에 걸쳐 도로의 정보를 나타내는 $u, v$ 가 주어진다. 이는 $u$번 사탕 가게와 $v$번 사탕 가게를 잇는 양방향 도로가 존재한다는 의미이다. ($1 \leq u, v \leq N$, $u \neq v$)
다음 줄에 친구의 수를 나타내는 정수 $M$이 주어진다. ($1 \leq M \leq 100\ 000$)
다음 $M$개 줄에 걸쳐 각 친구가 서 있는 가게의 번호와 좋아하는 사탕의 종류가 약속 시간이 빠른 순으로 주어진다. 여러 명의 친구가 같은 가게 앞에 서 있을 수도 있다.
약속 시간이 빠른 순서대로, 각 친구가 좋아하는 종류의 사탕을 사다 줄 수 있다면 PLAY
를, 아니라면 CRY
를 한 줄에 하나씩 출력한다.
5 1 2 3 4 5 1 2 1 3 2 4 2 5 4 3 5 4 2 5 3 3 4
PLAY PLAY CRY CRY
5 1 2 3 4 5 1 2 1 3 2 4 2 5 3 1 2 1 1 4 3
PLAY PLAY CRY
University > 서강대학교 > 2020 Sogang Programming Contest > Champion E번
University > 서강대학교 > 2020 Sogang Programming Contest > Open E번