30810번 - 페인트 칠하기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 79 | 29 | 25 | 34.247% |
문제
건물 $N$개와 도로 $M$개로 이루어진 도시가 있습니다. $i$번 도로는 $u_i$번 건물과 $v_i$번 건물을 양방향으로 잇습니다. 두 개 이상의 도로가 같은 건물 쌍을 서로 잇는 경우는 없습니다. 각 도로는 $K$가지 색의 유성 페인트 중 하나로 칠해져 있는데, $i$번 도로는 $c_i$번 색의 페인트로 칠해져 있습니다. 이 페인트는 아직 다 마르지 않았기 때문에, $i$번 도로를 거친 직후 방문한 건물은 $c_i$번 색으로 덮여 칠해질 것입니다. $(1\le i\le M)$처음에 모든 건물의 색은 $0$번 색입니다.
행위예술가 은하는 다음과 같은 방법으로 건물에 색을 칠하려고 합니다.
- 은하가 처음에 시작할 건물을 골라서 해당 건물로 갑니다.
- 모든 건물에 원하는 색이 칠해질 때까지 다음 단계를 반복합니다.
- 현재 있는 $a$번 건물에서, $p$번 색으로 칠해진 도로를 통해 인접한 $b$번 건물로 이동합니다. 같은 건물을 여러 번 방문해도 됩니다.
- $(a,b,p) =(u_i,v_i,c_i)$ 혹은 $(v_i,u_i,c_i)$인 $i$가 존재해야 합니다.
- $b$번 건물의 색을 이전에 칠해진 색과 관계없이 $p$번 색으로 덧칠합니다.
- 현재 있는 $a$번 건물에서, $p$번 색으로 칠해진 도로를 통해 인접한 $b$번 건물로 이동합니다. 같은 건물을 여러 번 방문해도 됩니다.
은하는 $1\le j\le N$인 모든 $j$에 대해 $j$번째 건물의 색을 $r_j$로 칠하려 합니다. 이것이 가능한지 판단하고, 가능하면 방법을 하나 출력하세요.
입력
첫 줄에 건물의 수 $N$, 도로의 수 $M$, 페인트 색의 수 $K$가 공백으로 구분되어 주어집니다. $(2 \le N \le 100\,000;$ $1 \le M \le 200\,000;$ $1 \le K \le 100\,000)$
둘째 줄에는 목표로 하는 건물 색을 의미하는 $r_1, r_2, \cdots, r_N$이 공백으로 구분되어 주어집니다. $(1 \le r_j \le K)$
다음 $M$개의 줄의 $i$번째 줄에는, 도로의 정보를 의미하는 $u_i, v_i, c_i$가 공백으로 구분되어 주어집니다. $(1 \le u_i < v_i \le N;$ $1 \le c_i \le K;$ $i \ne j \rightarrow (u_i, v_i) \ne (u_j, v_j) )$
주어지는 모든 입력은 정수입니다.
출력
$1\le j\le N$인 모든 $j$에 대해 $j$번째 건물의 색을 $r_j$로 칠할 수 있으면 첫 줄에 YES를, 아니면 NO를 출력하세요.
첫 줄에 YES를 출력했다면, 둘째 줄에 은하가 방문한 건물의 수를 출력한 후, 셋째 줄에 은하가 방문한 건물 번호를 방문한 순서로 공백으로 구분하여 출력하세요. 건물을 방문한 총 횟수는 $1\, 000\, 000$ 이하여야 하며, 해당 순서로 건물을 방문한 결과 $1\le j\le N$인 모든 $j$에 대해 $j$번째 건물의 색이 $r_j$여야 합니다. 목표대로 색을 칠할 수 있는 경우, 입력 조건을 만족하는 모든 입력에 대해 건물을 $1\, 000\, 000$번 이하로 방문하여 색을 칠할 수 있다는 것을 증명할 수 있습니다.
예제 입력 1
4 6 3 1 2 3 3 1 2 1 1 3 2 1 4 3 2 3 1 2 4 2 3 4 3
예제 출력 1
YES 5 4 3 4 2 1
예제 입력 2
4 2 3 1 1 3 3 1 2 1 3 4 3
예제 출력 2
NO
출처
Contest > solved.ac > solved.ac Grand Arena #3 > Division 2 G번
Contest > solved.ac > solved.ac Grand Arena #3 > Division 1 E번
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호