题目详情题解（0）讨论（0）提交记录（0）

AT_abc396_e.[ABC396E] Min of Restricted Sum

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定整数 N,MN, M 和长度为 MM 的整数序列 X=(X1,X2,…,XM)X=(X_1,X_2,\ldots,X_M)、Y=(Y1,Y2,…,YM)Y=(Y_1,Y_2,\ldots,Y_M)、Z=(Z1,Z2,…,ZM)Z=(Z_1,Z_2,\ldots,Z_M)。其中，保证 XX 和 YY 的所有元素均在 11 至 NN 的范围内。

定义长度为 NN 的非负整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) 为 好的整数序列，当且仅当满足以下条件：

  • 对于所有满足 1≤i≤M1 \leq i \leq M 的整数 ii，有 AXi⊕AYi=ZiA_{X_i} \oplus A_{Y_i} = Z_i，其中 ⊕\oplus 表示异或运算。

请判断是否存在这样的好的整数序列。若存在，请找出使得元素总和 ∑i=1NAi\displaystyle \sum_{i=1}^N A_i 最小的好的整数序列，并输出该序列。

关于异或（XOR）的定义：
对于非负整数 AA 和 BB，它们的异或 A⊕BA \oplus B 定义如下：

  • A⊕BA \oplus B 的二进制表示中，2k2^k 位（k≥0k \geq 0）的值为 11，当且仅当 AA 和 BB 在 2k2^k 位上的值不同；否则为 00。

例如，3⊕5=63 \oplus 5 = 6（二进制表示为 011⊕101=110011 \oplus 101 = 110）。

输入格式

输入通过标准输入给出，格式如下：

NN MM
X1X_1 Y1Y_1 Z1Z_1
X2X_2 Y2Y_2 Z2Z_2
⋮\vdots
XMX_M YMY_M ZMZ_M

输出格式

若不存在好的整数序列，输出 −1-1。
若存在，则输出满足总和最小的好的整数序列，元素间用空格分隔。
若存在多个总和最小的序列，输出任意一个均可。

输入输出样例

  • 输入#1

    3 2
1 3 4
1 2 3

    输出#1

    0 3 4

  • 输入#2

    3 3
1 3 4
1 2 3
2 3 5

    输出#2

    -1

  • 输入#3

    5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

    输出#3

    0 2 9 6 0

说明/提示

约束条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤M≤1050 \leq M \leq 10^5
  • 1≤Xi,Yi≤N1 \leq X_i, Y_i \leq N
  • 0≤Zi≤1090 \leq Z_i \leq 10^9
  • 输入中的所有值均为整数

样例解释 1

序列 A=(0,3,4)A=(0, 3, 4) 满足 A1⊕A2=3A_1 \oplus A_2 = 3 和 A1⊕A3=4A_1 \oplus A_3 = 4，因此是好的整数序列。其他可能的序列如 A=(1,2,5)A=(1, 2, 5) 或 A=(7,4,3)A=(7, 4, 3) 也满足条件，但总和最小的序列是 A=(0,3,4)A=(0, 3, 4)。

样例解释 2

不存在满足条件的好的整数序列，因此输出 −1-1。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页