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

CodeForces Gym

Provider CodeForces Gym

Origin 2021 ICPC Asia Taiwan Online Programming Contest

Code GYM103373H

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:09

Related

Nothing Yet