Universal Cup Judging System

Universal Cup

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

Cho một đồ thị vô hướng gồm $n$ đỉnh, ban đầu đồ thị không có cạnh nào. Hãy thực hiện $q$ thao tác thuộc hai loại sau:

  • $+\ u\ v\ w$: Thêm một cạnh nối hai đỉnh $u$ và $v$ với trọng số là $w$.
  • $?\ u\ v$: Định nghĩa trọng số của một đường đi là phép AND theo bit (bitwise-and) của trọng số tất cả các cạnh trên đường đi đó. Hãy tính trọng số lớn nhất có thể của một đường đi bắt đầu từ đỉnh $u$ và kết thúc tại đỉnh $v$. Nếu không có đường đi nào nối hai đỉnh $u$ và $v$, câu trả lời sẽ là $-1$.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 100$) biểu thị số lượng bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($2 \le n \le 10^3$, $1 \le q \le 10^6$) lần lượt biểu thị số lượng đỉnh và số lượng thao tác.

Trong $q$ dòng tiếp theo, dòng thứ $i$ trước hết chứa một ký tự $op$ ($op \in \{+, ?\}$) biểu thị loại truy vấn thứ $i$.

  • Nếu $op = +$, theo sau là ba số nguyên $u$, $v$ và $w$ ($1 \le u, v \le n$, $0 \le w < 2^{12}$), biểu thị một thao tác loại một.
  • Nếu $op = ?$, theo sau là hai số nguyên $u$ và $v$ ($1 \le u, v \le n$, $u \ne v$), biểu thị một thao tác loại hai.

Dữ liệu đảm bảo có ít nhất một thao tác loại hai trong mỗi bộ dữ liệu. Ngoài ra, tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $10^3$, và tổng của $q$ trong tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Để giảm kích thước dữ liệu ra, với mỗi bộ dữ liệu chỉ cần in ra một dòng chứa một số nguyên là tổng các câu trả lời cho tất cả các thao tác loại hai.

Ví dụ

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

Ghi chú

Ở bộ dữ liệu mẫu đầu tiên, câu trả lời cho các thao tác loại hai lần lượt là $2$, $3$, $4$, $2$ và $6$.

Ở bộ dữ liệu mẫu thứ hai, câu trả lời cho các thao tác loại hai lần lượt là $64$ và $-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.