Preparing NOJ

# A Hard Problem

15000ms 1048576K

## Description:

You are given a simple undirected graph consisting of $n$ nodes and $m$ edges. The nodes are numbered from $1$ to $n$, and the edges are numbered from $1$ to $m$. Node $i$ has a non-negative integer value $V_i$ and the weight $W_{u,v}$ of edge $\{u, v\}$ is defined as $\left\|V_u\oplus V_v\right\|$ where $\oplus$ is the exclusive-or operator (equivalent to ^ in C) and $\|x\|$ is the number of set bits in the binary representation non-negative integer $x$

The node values $V_1,V_2,\dots,V_n$ must satisfy $q$ constraints. Each of the constraints can be represented as a 5-tuple $(t,u,i,v,j)$.

• if $t = 0$, then $getBit(V_u, i) = getBit(V_v, j)$
• if $t = 1$, then $getBit(V_u, i) \neq getBit(V_v, j)$
where the function $getBit(x, i)$ returns the $(i+1)$-th least significant bit of $x$. For examples, $getBit(11, 0)$ is $1$ and $getBit(11,2)=0$. In the C programming language, $getBit(x, i)$ can be computed by ((x ยป i) & 1U) if $x$ is a 32-bit unsigned integer and $i$ is a non-negative integer at most $31$.

Unfortunately, some node values are missing now. Your task is to assign new values to them to minimize $\sum_{\{u,v\} \in E}W_{u,v}$ without violating any given constraint. Please write a program to help yourself to complete this task.

## Input:

The input consists of five parts. The first part contains one line, and that line contains two positive integers $n$ and $m$. $n$ is the number of nodes, and $m$ is the number of edges. The second part contains $m$ lines. Each of them contains two integers $u$ and $v$, indicating an edge $\{u, v\}$ of the given graph. The third part contains one line. That line consists of $n$ space-separated integers $x_1,x_2,\dots,x_n$. For any $k\in\{1,2,\dots,n\}$, if the node value $V_k$ is missing, $x_k$ will be -1; otherwise, $V_k$ is $x_k$. The fourth part contains one integer $q$, indicating the number of constraints. The fifth part contains $q$ lines, and each of them contains five space-separated integers $t, u, i, v, j$ indicating that $(t, u, i, v, j)$ is a constraint.

• $1 \le n \le 1000$
• $1 \le m \le 5000$
• $-1 \le V_i < 2^{16}$
• $0 \le q \le 8$
• $t \in \{0, 1\}$
• $0 \le u, v < n$
• $0 \le i, j < 16$

## Output:

Output an integer which is the minimum value under the $q$ constraints. If it is not possible to satisfy all the constraints, output -1.

## Sample Input:

4 4
1 3
1 2
3 2
0 3
-1 -1 60091 51514 2
1 2 0 1 5
0 2 6 0 15


## Sample Output:

13


## Sample Input:

3 2
0 1
1 2
-1 -1 -1
2 1 2 0 1 5
0 1 5 2 0


## Sample Output:

-1


Info

Provider CodeForces Gym

Code GYM103373H

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:09

Related

Nothing Yet