| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 512 MB | 36 | 22 | 15 | 53.571% |
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.
| 번호 | 배점 | 제한 |
|---|---|---|
| 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 |
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 0
For the first graph, the operations needed are: