Universal Cup Judging System

Universal Cup

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

畀定一個有 $n$ 個頂點嘅無向圖,一開始張圖入面冇任何邊。請維護 $q$ 次以下兩種類型嘅操作:

  • $+\ u\ v\ w$:加入一條連接頂點 $u$ 同 $v$、邊權為 $w$ 嘅邊。
  • $?\ u\ v$:將一條路徑嘅權重定義為路徑上所有邊嘅權重嘅按位與(bitwise-and)。計算由頂點 $u$ 出發並喺頂點 $v$ 結束嘅路徑嘅最大可能權重。如果唔存在連接頂點 $u$ 同 $v$ 嘅路徑,答案應為 $-1$。

輸入格式

輸入包含多組測試資料。輸入嘅第一行包含一個整數 $T$($1 \le T \le 100$),表示測試資料嘅組數。對於每組測試資料:

第一行包含兩個整數 $n$ 同 $q$($2 \le n \le 10^3$,$1 \le q \le 10^6$),分別表示頂點嘅數量同操作嘅數量。

接落嚟嘅 $q$ 行,第 $i$ 行首先包含一個字元 $op$($op \in \{+, ?\}$),表示第 $i$ 次詢問嘅類型。

  • 如果 $op = +$,接住會有三個整數 $u$、$v$ 同 $w$($1 \le u, v \le n$,$0 \le w < 2^{12}$),表示第一種類型嘅操作。
  • 如果 $op = ?$,接住會有兩個整數 $u$ 同 $v$($1 \le u, v \le n$,$u \ne v$),表示第二種類型嘅操作。

題目保證每組測試資料至少有一次第二種類型嘅操作。同時,所有測試資料嘅 $n$ 總和唔超過 $10^3$,所有測試資料嘅 $q$ 總和唔超過 $10^6$。

輸出格式

為咗減細輸出量,對於每組測試資料,只需輸出一行一個整數,表示所有第二種類型操作嘅答案總和。

範例

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

說明

對於第一組範例測試資料,第二種類型操作嘅答案依序為 $2$、$3$、$4$、$2$ 同 $6$。

對於第二組範例測試資料,第二種類型操作嘅答案依序為 $64$ 同 $-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.