25202번 - Colors 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 1 | 1 | 1 | 100.000% |
문제
Consider a connected undirected graph with N nodes and M edges. Initially every node u has a color a[u], encoded by an integer between 1 and N. You can repeatedly modify node colors by assigning a[u] = min(a[u], a[v]), where u and v are connected by an edge.
Given a destination coloring b[1] ... b[N], determine whether you can transform a into b.
입력
There are several test cases per input file and you should answer each of them separately.
The first line contains the number of test cases. Each test case is structured as
N M a[1] a[2] ... a[N] b[1] b[2] ... b[N] u1 v1 u2 v2 ... uM vM
출력
For every test case you should print, on a separate line, 1 if a can be transformed into b using the above-mentioned operation and 0 otherwise.
제한
- For all test cases, N ≤ 150,000 and M ≤ 200,000.
- For every input file, the sum of all N ≤ 300,000 and the sum of all M ≤ 400,000.
- 1 ≤ a[i], b[i] ≤ N for all 1 ≤ i ≤ N.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | The graph is a star (M = N - 1 and one node is connected to every other node). The sum of N2 among all test cases in an input file ≤ 5,000,000. |
| 2 | 7 | The graph is complete. N ≤ 50. The sum of N × M among all test cases in an input file ≤ 12,000,000. |
| 3 | 8 | The graph is a chain (M = N - 1 and the edges form a single path). The sum of N2 among all test cases in an input file ≤ 5,000,000. |
| 4 | 15 | The graph is a chain, no further constraints. |
| 5 | 7 | The graph is a tree. The sum of N2 among all test cases in an input file ≤ 5,000,000. |
| 6 | 16 | The graph is a tree and the coloring a is a permutation of {1, 2, ..., N}. |
| 7 | 10 | The sum of N × M among all test cases in an input file ≤ 5,000,000. |
| 8 | 22 | none |
예제 입력 1
2 4 4 3 3 2 1 2 1 2 1 1 2 2 3 3 4 4 2 4 4 3 3 2 1 1 2 2 1 1 2 2 3 3 4 4 2
예제 출력 1
1 0
For the first graph, the operations needed are:
- a[2] = min(a[2], a[3]) = 2
- a[1] = min(a[1], a[2]) = 2
- a[2] = min(a[2], a[4]) = 1
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호