Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.5 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

On vous donne un graphe non orienté à $n$ sommets, qui ne contient initialement aucune arête. Vous devez traiter $q$ opérations des deux types suivants :

  • $+\ u\ v\ w$ : Ajouter une arête reliant les sommets $u$ et $v$, de poids $w$.
  • $?\ u\ v$ : On définit le poids d'un chemin comme le ET bit à bit (bitwise-and) des poids de toutes les arêtes du chemin. Calculez le poids maximal possible d'un chemin partant du sommet $u$ et se terminant au sommet $v$. S'il n'existe aucun chemin reliant les sommets $u$ et $v$, la réponse doit être $-1$.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) indiquant le nombre de sommets et le nombre d'opérations.

Pour les $q$ lignes suivantes, la $i$-ème ligne commence par un caractère $op$ ($op \in \{+, ?\}$) indiquant le type de la $i$-ème requête.

  • Si $op = +$, trois entiers $u$, $v$ et $w$ suivent ($1 \le u, v \le n$, $0 \le w < 2^{12}$), indiquant une opération du premier type.
  • Si $op = ?$, deux entiers $u$ et $v$ suivent ($1 \le u, v \le n$, $u \ne v$), indiquant une opération du second type.

Il est garanti qu'il y a au moins une opération du second type pour chaque cas de test. De plus, la somme de $n$ sur tous les cas de test ne dépasse pas $10^3$, et la somme de $q$ sur tous les cas de test ne dépasse pas $10^6$.

Sortie

Pour réduire la taille de la sortie, affichez simplement pour chaque cas de test une ligne contenant un seul entier, indiquant la somme des réponses à toutes les opérations du second type.

Exemples

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

Remarque

Pour le premier cas de test de l'exemple, les réponses aux opérations du second type sont $2$, $3$, $4$, $2$ et $6$.

Pour le second cas de test de l'exemple, les réponses aux opérations du second type sont $64$ et $-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.