Even Path (Problem C, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Vincentius Madya Putra Indrawan

# Problem Statement

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.

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$.

A path in this maze is defined as a sequence of cells $(r_1, c_1), (r_2, c_2), \ldots, (r_k, c_k)$ such that $|r_i - r_{i+1}| + |c_i - c_{i+1}| = 1$ for all $1 \leq i < 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.

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.

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$.

|+|3|4|8|5|1|
|---|---|---|---|---|---|
|6|9|10|14|11|7|
|2|5|6|10|7|3|
|7|10|11|15|12|8|
|8|11|12|16|13|9|
|3|6|7|11|8|4|

Let us consider several queries:

- ⟨2, 2, 1, 3⟩: 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.

- ⟨4, 2, 4, 3⟩: There is an even path from cell $(4, 2)$ to cell $(4, 3)$, namely $(4, 2), (4, 3)$.

- ⟨5, 1, 3, 4⟩: 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)$.

# Input

Input begins with a line containing two integers: $N\ Q$ ($2 \leq N \leq 100\ 000$; $1 \leq Q \leq 100\ 000$) representing the size of the maze and the number of queries, respectively. The next line contains $N$ integers: $R_i$ ($0 \leq R_i \leq 10^6$) representing the array $R$. The next line contains $N$ integers: $C_i$ ($0 \leq C_i \leq 10^6$) representing the array $C$. The next $Q$ lines each contains four integers: $r_a\ c_a\ r_b\ c_b$ ($1 \leq r_a, c_a, r_b, c_b \leq 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.

# Output

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)$.

# Sample Input #1
```
5 3
6 2 7 8 3
3 4 8 5 1
2 2 1 3
4 2 4 3
5 1 3 4
```
# Sample Output #1
```
YES
YES
NO
```
# Explanation for the sample input/output #1: 
This is the example from the problem description.

# Sample Input #2
```
3 2
30 40 49
15 20 25
2 2 3 3
1 2 2 2
```
# Sample Output #2
```
NO
YES
```

Sample inputs:
5 3
6 2 7 8 3
3 4 8 5 1
2 2 1 3
4 2 4 3
5 1 3 4

3 2
30 40 49
15 20 25
2 2 3 3
1 2 2 2

Sample outputs:
YES
YES
NO

NO
YES

# Solution Analysis
Analysis author: Wiwit Rifai'

**Observe** that we can go from cell $(r, c)$ to cell $(r \pm 1, c)$ only if the parity of $R[r]$ and the target cell (i.e. $R[r \pm 1]$) are the same because there is only one element changing, i.e. $R[r]$ to $R[r \pm 1]$. Similar things also happened with the column. We can go from cell $(r, c)$ to cell $(r, c \pm 1)$ only if the parity of $C[c]$ and the target cell (i.e. $C[c \pm 1]$) are the same.

Therefore, for each query $\langle r_a, c_a, r_b, c_b \rangle$, we only need to check whether the parity of $R[r]$ are the same for all $r = \min(r_a, r_b)..\max(r_a, r_b)$, and whether the parity of $C[c]$ are the same for all $c = \min(c_a, c_b)..\max(c_a, c_b)$.  
Do a precomputation first (in $\mathcal{O}(N)$) before processing any query so that we can decide whether $R[i..j]$ or $C[i..j]$ have the same parity in $\mathcal{O}(1)$ for all pair of $i$ and $j$. You can use a union-find data structure to do this, although it is overkill; there is another much simpler ad-hoc method to find the groups involving only one iteration. The time complexity for this solution is $\mathcal{O}(N + Q)$.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}