Universal Cup Judging System

Universal Cup

시간 제한: 2.5 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

$n$ 個の頂点を持つ無向グラフが与えられます。初期状態ではグラフに辺はありません。以下の 2 種類の操作を $q$ 回処理してください。

  • $+\ u\ v\ w$: 頂点 $u$ と頂点 $v$ を結ぶ重み $w$ の辺を追加する。
  • $?\ u\ v$: パスの重みを、そのパスに含まれるすべての辺の重みのビット毎論理積(bitwise-and)として定義する。頂点 $u$ から始まり頂点 $v$ で終わるパスの重みとしてあり得る最大値を求める。頂点 $u$ と頂点 $v$ を結ぶパスが存在しない場合、答えは $-1$ とする。

入力

複数のテストケースが与えられます。入力の 1 行目にはテストケースの個数を表す整数 $T$($1 \le T \le 100$)が与えられます。各テストケースについて:

1 行目には頂点数と操作数を表す 2 つの整数 $n$ と $q$($2 \le n \le 10^3$、$1 \le q \le 10^6$)が与えられます。

続く $q$ 行のうち $i$ 行目には、まず $i$ 番目のクエリの種類を表す文字 $op$($op \in \{+, ?\}$)が与えられます。

  • $op = +$ の場合、続いて 3 つの整数 $u$、$v$、$w$($1 \le u, v \le n$、$0 \le w < 2^{12}$)が与えられ、1 種類目の操作を表します。
  • $op = ?$ の場合、続いて 2 つの整数 $u$ と $v$($1 \le u, v \le n$、$u \ne v$)が与えられ、2 種類目の操作を表します。

各テストケースには 2 種類目の操作が少なくとも 1 つ含まれることが保証されます。また、すべてのテストケースにおける $n$ の総和は $10^3$ を超えず、$q$ の総和は $10^6$ を超えません。

出力

出力サイズを削減するため、各テストケースについて 1 行に 1 つの整数を出力してください。これは 2 種類目の操作すべてに対する答えの総和を表します。

入出力例

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

注記

1 つ目のサンプルテストケースでは、2 種類目の操作に対する答えは順に $2$、$3$、$4$、$2$、$6$ です。

2 つ目のサンプルテストケースでは、2 種類目の操作に対する答えは順に $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.