Universal Cup Judging System

Universal Cup

حد الوقت: 2.5 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

$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$-ші жолында алдымен $i$-ші сұранымның түрін білдіретін $op$ ($op \in \{+, ?\}$) таңбасы беріледі.

  • Егер $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.