P5292 [HNOI2019] Campus Tour

HNOI2019 Day2T1

Each building in a school has a unique ID. One day, you feel bored and decide to wander around the campus. You have stayed on campus for a while and are very familiar with the IDs of all buildings, so you cannot help writing down the IDs of every nearby building. However, you do not really write down the IDs; instead, you take each building’s ID modulo $2$, getting $0$ or $1$ as the label of that building. Concatenating the labels of multiple buildings forms a 01 string. You are very interested in this string, especially when it is a palindrome, so you decide to study this problem. The school can be considered as a graph: buildings are vertices, and there are undirected edges between some pairs of vertices. Each vertex has a label ($0$ or $1$). Each time, you choose two vertices in the graph, and you want to know whether there exists a path between these two vertices such that the labels of the vertices visited along the path form a palindrome string. A palindrome string is a string that is the same after being reversed. For example, “010” and “1001” are palindromes, while “01” and “110” are not. Note that a string of length $1$ is always a palindrome, so if the two queried vertices are the same, such a path always exists. Also note that the path does not have to be a simple path, meaning each edge and each vertex may be visited any number of times.

The input file name is tour.in. The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of queries. The second line is a 01 string of length $n$, where the $i$-th character represents the label of the $i$-th vertex (i.e., vertex $i$). Vertices are numbered starting from $1$. The next $m$ lines each contain two integers $u_i, v_i$, indicating that there is an undirected edge between vertex $u_i$ and vertex $v_i$. There are no self-loops or multiple edges. The next $q$ lines each contain two integers $x_i, y_i$, asking whether there exists a valid path between vertex $x_i$ and vertex $y_i$.

The output file name is tour.out. Output $q$ lines. Each line contains the string “YES” or “NO” (without quotes). Output “YES” if such a path exists, and “NO” otherwise.

[Sample Explanation 1] For the first query, vertex $3$ and vertex $2$ are not connected, so the answer is “NO”. For the second query, one valid path is $1\to 3$, and the string formed by the labels on the path is “00”. Note that the valid path is not unique. [Constraints] For $30\%$ of the testdata, $1 \leq m \leq 10 ^ 4$. For $70\%$ of the testdata, $1 \leq n \leq 3000$, $1 \leq m \leq 5\times 10 ^ 4$. For $100\%$ of the testdata, $1 \leq n \leq 5000$, $1 \leq m \leq 5\times 10 ^ 5$, $1 \leq q \leq 10 ^ 5$. [Compile Commands] For C++: g++ -o tour tour.cpp –lm -O2 For C: gcc -o tour tour.c –lm -O2 For Pascal: fpc tour.pas -O2 Translated by ChatGPT 5