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.