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

Givet en oriktad graf med $n$ hörn, som från början saknar kanter. Hantera $q$ operationer av följande två typer:

  • $+\ u\ v\ w$: Lägg till en kant som förbinder hörnen $u$ och $v$, med vikten $w$.
  • $?\ u\ v$: Definiera vikten av en väg som det bitvisa OCH-värdet (bitwise-and) av vikterna för alla kanter längs vägen. Beräkna den största möjliga vikten för en väg som startar i hörn $u$ och slutar i hörn $v$. Om det inte finns någon väg som förbinder hörnen $u$ och $v$ ska svaret vara $-1$.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$) som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $n$ och $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) som anger antalet hörn och antalet operationer.

För de följande $q$ raderna innehåller den $i$-te raden först ett tecken $op$ ($op \in \{+, ?\}$) som anger typen för den $i$-te frågan.

  • Om $op = +$ följer tre heltal $u$, $v$ och $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), vilket anger en operation av den första typen.
  • Om $op = ?$ följer två heltal $u$ och $v$ ($1 \le u, v \le n$, $u \ne v$), vilket anger en operation av den andra typen.

Det garanteras att det finns minst en operation av den andra typen i varje testfall. Dessutom överstiger summan av $n$ över alla testfall inte $10^3$, och summan av $q$ över alla testfall överstiger inte $10^6$.

Utdata

För att minska storleken på utdatan ska du för varje testfall bara skriva ut en rad med ett enda heltal, som anger summan av svaren på alla operationer av den andra typen.

Exempel

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

Förklaring

För det första exempeltestfallet är svaren på operationerna av den andra typen $2$, $3$, $4$, $2$ och $6$.

För det andra exempeltestfallet är svaren på operationerna av den andra typen $64$ och $-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.