DMOPC '17 Contest 5 P5 - XOR Bridges - DMOJ: Modern Online Judge

DMOPC '17 Contest 5 P5 - XOR Bridges

Points: 15 (partial)

Time limit: 2.5s

Memory limit: 256M

Author:

Problem types

In a distant land, there are $N$ $N$ islands. Each island has a value of accessibility denoted by $v_i$ $v_{i}$ . You are a bridge building contractor that has been given the task of trying to connect the islands by building bridges. However, because you want to save resources, you have decided to only build bridges such that the XOR of the accessibilities of the islands you connect with a bridge, is less than or equal to $M$ $M$ . That is, you will build a bridge between island $i$ $i$ and $j$ $j$ if and only if $v_i \oplus v_j \le M$ $v_{i} \oplus v_{j} \leq M$ . Now, your boss has given you $Q$ $Q$ queries, each asking if islands $p_i$ $p_{i}$ and $q_i$ $q_{i}$ will be connected by the bridges.

Constraints

For all subtasks:
$1 \le N, Q \le 200\,000$ $1 \leq N, Q \leq 200 000$
$0 \le M, v_i \le 10^9$ $0 \leq M, v_{i} \leq 10^{9}$
$1 \le p_i, q_i \le N$ $1 \leq p_{i}, q_{i} \leq N$

Subtask 1 [5%]

$1 \le N, Q \le 100$ $1 \leq N, Q \leq 100$
$0 \le M, v_i \le 100$ $0 \leq M, v_{i} \leq 100$

Subtask 2 [5%]

$1 \le N, Q \le 5\,000$ $1 \leq N, Q \leq 5 000$
$0 \le M \le 5\,000$ $0 \leq M \leq 5 000$

Subtask 3 [10%]

$M = 2^k-1$ $M = 2^{k} - 1$ for some non-negative integer $k$ $k$ and $0 \le M \le 10^9$ $0 \leq M \leq 10^{9}$ .

Subtask 4 [80%]

No additional constraints.

Input Specification

The first line contains three space-separated integers $N, M, Q$ $N, M, Q$ .
The second line contains $N$ $N$ space-separated integers, $v_i$ $v_{i}$ , denoting the accessibility of island $i$ $i$ .
The next $Q$ $Q$ lines contain two space-separated integers $p_i$ $p_{i}$ and $q_i$ $q_{i}$ , a query asking if islands $p_i$ $p_{i}$ and $q_i$ $q_{i}$ are connected by a set of bridges.

Output Specification

For each of the queries, print YES if the islands are connected, or NO otherwise.

Sample Input

Copy

Sample Output

Copy

NO
YES
NO
YES

Comments

0

anasschoukri2 commented on March 15, 2018, 7:13 p.m.

how can I deal with bad_alloc ??

3

r3mark commented on March 15, 2018, 7:37 p.m.

You're using too much memory. You can pass the first two subtasks by making your array sizes smaller, but your approach won't work for subtasks 3 and 4.