Universal Cup Judging System

Universal Cup

Time Limit: 2.5 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

È dato un grafo non orientato con $n$ vertici; inizialmente il grafo non ha archi. Gestisci $q$ operazioni dei seguenti due tipi:

  • $+\ u\ v\ w$: Aggiungi un arco che collega i vertici $u$ e $v$, con peso $w$.
  • $?\ u\ v$: Definisci il peso di un cammino come l'AND bit a bit (bitwise-and) dei pesi di tutti gli archi nel cammino. Calcola il massimo peso possibile di un cammino che inizia dal vertice $u$ e termina nel vertice $v$. Se non esiste alcun cammino che collega i vertici $u$ e $v$, la risposta deve essere $-1$.

Dati di ingresso

Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 100$) che indica il numero di casi di test. Per ciascun caso di test:

La prima riga contiene due interi $n$ e $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) che indicano il numero di vertici e il numero di operazioni.

Per le successive $q$ righe, la $i$-esima riga contiene innanzitutto un carattere $op$ ($op \in \{+, ?\}$) che indica il tipo della $i$-esima query.

  • Se $op = +$, seguono tre interi $u$, $v$ e $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), che indicano un'operazione del primo tipo.
  • Se $op = ?$, seguono due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$), che indicano un'operazione del secondo tipo.

È garantito che ci sia almeno un'operazione del secondo tipo per ogni caso di test. Inoltre, la somma di $n$ su tutti i casi di test non supera $10^3$, e la somma di $q$ su tutti i casi di test non supera $10^6$.

Dati di uscita

Per ridurre la dimensione dell'output, per ciascun caso di test stampa semplicemente una riga contenente un solo intero, che indica la somma delle risposte a tutte le operazioni del secondo tipo.

Esempi

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

Note

Per il primo caso di test di esempio, le risposte alle operazioni del secondo tipo sono $2$, $3$, $4$, $2$ e $6$.

Per il secondo caso di test di esempio, le risposte alle operazioni del secondo tipo sono $64$ e $-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.