codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1252C.md (3667B)


      1 Source: https://codeforces.com/problemset/problem/1252/C
      2 
      3 C. Even Path
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Pathfinding is a task of finding a route between two points. It often appears in many problems. For example, in a GPS navigation software where a driver can query for a suggested route, or in a robot motion planning where it should find a valid sequence of movements to do some tasks, or in a simple maze solver where it should find a valid path from one point to another point. This problem is related to solving a maze.
     22 
     23 The maze considered in this problem is in the form of a matrix of integers $A$ of $N \times N$. The value of each cell is generated from a given array $R$ and $C$ of $N$ integers each. Specifically, the value on the $i^{th}$ row and $j^{th}$ column, cell $(i,j)$, is equal to $R_i + C_j$. Note that all indexes in this problem are from $1$ to $N$.
     24 
     25 A path in this maze is defined as a sequence of cells $(r_1,c_1), (r_2,c_2), \dots, (r_k,c_k)$ such that $|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1$ for all $1 \le i \lt k$. In other words, each adjacent cell differs only by $1$ row or only by $1$ column. An even path in this maze is defined as a path in which all the cells in the path contain only even numbers.
     26 
     27 Given a tuple $\langle r_a,c_a,r_b,c_b \rangle$ as a query, your task is to determine whether there exists an even path from cell $(r_a,c_a)$ to cell $(r_b,c_b)$. To simplify the problem, it is guaranteed that both cell $(r_a,c_a)$ and cell $(r_b,c_b)$ contain even numbers.
     28 
     29 For example, let $N = 5$, $R = \{6, 2, 7, 8, 3\}$, and $C = \{3, 4, 8, 5, 1\}$. The following figure depicts the matrix $A$ of $5 \times 5$ which is generated from the given array $R$ and $C$.
     30 
     31  ![](https://espresso.codeforces.com/6b5e0abfb808bbde1d8107e036d5b3d752ff8625.png) 
     32 
     33 Let us consider several queries:
     34 
     35 * $\langle 2, 2, 1, 3 \rangle$: There is an even path from cell $(2,2)$ to cell $(1,3)$, e.g., $(2,2), (2,3), (1,3)$. Of course, $(2,2), (1,2), (1,3)$ is also a valid even path.
     36 * $\langle 4, 2, 4, 3 \rangle$: There is an even path from cell $(4,2)$ to cell $(4,3)$, namely $(4,2), (4,3)$.
     37 * $\langle 5, 1, 3, 4 \rangle$: There is no even path from cell $(5,1)$ to cell $(3,4)$. Observe that the only two neighboring cells of $(5,1)$ are cell $(5,2)$ and cell $(4,1)$, and both of them contain odd numbers (7 and 11, respectively), thus, there cannot be any even path originating from cell $(5,1)$.
     38 
     39 Input
     40 
     41 Input begins with a line containing two integers: $N$ $Q$ ($2 \le N \le 100\,000$; $1 \le Q \le 100\,000$) representing the size of the maze and the number of queries, respectively. The next line contains $N$ integers: $R_i$ ($0 \le R_i \le 10^6$) representing the array $R$. The next line contains $N$ integers: $C_i$ ($0 \le C_i \le 10^6$) representing the array $C$. The next $Q$ lines each contains four integers: $r_a$ $c_a$ $r_b$ $c_b$ ($1 \le r_a, c_a, r_b, c_b \le N$) representing a query of $\langle r_a, c_a, r_b, c_b \rangle$. It is guaranteed that $(r_a,c_a)$ and $(r_b,c_b)$ are two different cells in the maze and both of them contain even numbers.
     42 
     43 Output
     44 
     45 For each query in the same order as input, output in a line a string "YES" (without quotes) or "NO" (without quotes) whether there exists an even path from cell $(r_a,c_a)$ to cell $(r_b,c_b)$.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 5 3
     53 6 2 7 8 3
     54 3 4 8 5 1
     55 2 2 1 3
     56 4 2 4 3
     57 5 1 3 4
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 YES
     64 YES
     65 NO
     66 ```
     67 
     68 Input
     69 
     70 ```
     71 3 2
     72 30 40 49
     73 15 20 25
     74 2 2 3 3
     75 1 2 2 2
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 NO
     82 YES
     83 ```
     84 
     85 Note
     86 
     87 Explanation for the sample input/output #1
     88 
     89 This is the example from the problem description.