CERC2010 E - Enter The Dragon- 물먹는 용(Enter The Dragon) > 문제은행 : 정보올림피아드&알고리즘



1285 : 물먹는 용(Enter The Dragon)

제한시간
3000 ms   
메모리제한
128 MB   
해결횟수
15 회   
시도횟수
86 회   

문제

아데니아의 수도는 여러 개의 도시로 이루어져 있다. 각 도시는 하나의 호수를 갖고 있으며 호수 주변에 형성되어 있다. 

최근 많은 비가 내릴 것으로 예상되는데 각각의 도시는 호수의 물을 비우면 홍수가 나지 않지만 호수를 비우지 못한 도시는 홍수피해를 입게 된다. 

초기에 모든 호수에는 물이 차 있다.


그런데 다행스럽게도 아데니아에는 전설의 물먹는 하마 아니 물먹는 용 참견스가 살고 있다고 한다. 

여러분도 알다시피 참견스는 호수 옆에 앉아 한번 들이키면 호수의 물을 모두 말라 버리게 할 수 있다. 

참견스의 배는 무한대라서 얼마든지 호수를 비울 수 있지만 비가 내리는 날에는 어느 호수의 물도 마시지 않는다고 한다. 

아데니아에는 예언자가 있어 오늘 이 후 여러 날 동안의 날씨를 예측할 수 있다고 한다.

 

여러분이 해야 할 일은 예측된 일기 예보가 주어질 때, 어느 날에 어느 호수의 물을 참견스가 먹어야 할지 계산하는 것이다. 


입력형식

입력은 4개의 TestCase로 구성되며 각 TestCase의 구성은 다음과 같다.

첫 행에 호수의 개수 N과 M( 1 <= N, M <= 10^6)이 공백으로 구분하여 주어진다. 

N은 호수의 수이고 M은 예측된 일기 예보의 개수이다. 

두 번째 행에 M개의 정수 P_k가 공백을 구분하여 주어진다. 

P_k가 0인 경우에는 k번째 날에는 비가 오지 않는 날이고 P_k가 1인 경우 k번째 날에는 1번 호수에,

P_k가 2인 경우에 k번째 날에는 2번 호수에 등등... 비가 내린다.


출력형식

아데니아의 모든 도시에 홍수가 발생하지 않는 경우 첫 행에 YES를 출력하고

다음 행에는 비가오지 않는 날에 참견스가 호수의 물을 마시게 되면 호수의 번호를, 

마시지 않을 경우에는 0을 공백을 구분하여 출력한다. 

 

가능한 경우가 여러 가지라면 그 중 한 가지만 출력한다. 

어느 한 도시라도 홍수가 발생하면 첫 행에 NO만 출력한다.


입력 예

2 4
0 0 1 1
2 4
0 1 0 2
2 3
0 1 2
2 4
0 0 0 1

출력 예

NO
YES
1 2
NO
YES
0 1 0


set, map, union-find

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP