Universal Cup Judging System

Universal Cup

Limite de temps : 2.5 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Se da un grafo no dirigido con $n$ vértices; inicialmente el grafo no tiene aristas. Mantén $q$ operaciones de los siguientes dos tipos:

  • $+\ u\ v\ w$: Añade una arista que conecte los vértices $u$ y $v$, con un peso de $w$.
  • $?\ u\ v$: Define el peso de un camino como el AND bit a bit (bitwise-and) de los pesos de todas las aristas en el camino. Calcula el mayor peso posible de un camino que comience en el vértice $u$ y termine en el vértice $v$. Si no existe ningún camino que conecte los vértices $u$ y $v$, la respuesta debe ser $-1$.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) que indican el número de vértices y el número de operaciones.

En las siguientes $q$ líneas, la $i$-ésima línea contiene primero un carácter $op$ ($op \in \{+, ?\}$) que indica el tipo de la $i$-ésima consulta.

  • Si $op = +$, siguen tres enteros $u$, $v$ y $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), indicando una operación del primer tipo.
  • Si $op = ?$, siguen dos enteros $u$ y $v$ ($1 \le u, v \le n$, $u \ne v$), indicando una operación del segundo tipo.

Se garantiza que hay al menos una operación del segundo tipo en cada caso de prueba. Además, la suma de $n$ en todos los casos de prueba no supera $10^3$, y la suma de $q$ en todos los casos de prueba no supera $10^6$.

Salida

Para reducir el tamaño de la salida, para cada caso de prueba imprime únicamente una línea con un entero, indicando la suma de las respuestas a todas las operaciones del segundo tipo.

Ejemplos

2
4 11
+ 1 3 6
+ 3 4 2
? 1 4
+ 1 4 3
? 4 1
+ 4 3 4
? 1 4
+ 3 2 3
? 1 2
+ 1 1 4
? 1 3
4 4
+ 1 2 64
+ 3 4 32
? 1 2
? 3 1
17
63

Nota

Para el primer caso de prueba de ejemplo, las respuestas a las operaciones del segundo tipo son $2$, $3$, $4$, $2$ y $6$.

Para el segundo caso de prueba de ejemplo, las respuestas a las operaciones del segundo tipo son $64$ y $-1$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.