AT_abc277_h [ABC277Ex] Constrained Sums

题目描述

判断是否存在一个长度为 $N$ 的整数序列 $X = (X_1, X_2, \ldots, X_N)$，使其满足以下所有条件。如果存在，输出其中一种构造方式。

• 对于所有 $1 \leq i \leq N$，有 $0 \leq X_i \leq M$。
• 对于所有 $1 \leq i \leq Q$，有 $L_i \leq X_{A_i} + X_{B_i} \leq R_i$。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $Q$
$A_1$ $B_1$ $L_1$ $R_1$
$A_2$ $B_2$ $L_2$ $R_2$
$\vdots$
$A_Q$ $B_Q$ $L_Q$ $R_Q$

输出格式

如果存在满足题目所有条件的整数序列，则输出其中一种 $X_1, X_2, \ldots, X_N$，以空格分隔。如果不存在，输出 -1。

输入输出样例 #1

输入 #1

4 5 3
1 3 5 7
1 4 1 2
2 2 3 8

输出 #1

2 4 3 0

输入输出样例 #2

输入 #2

3 7 3
1 2 3 4
3 1 9 12
2 3 2 4

输出 #2

-1

说明/提示

限制条件

• $1 \leq N \leq 10000$
• $1 \leq M \leq 100$
• $1 \leq Q \leq 10000$
• $1 \leq A_i, B_i \leq N$
• $0 \leq L_i \leq R_i \leq 2 \times M$
• 输入均为整数

样例解释 1

当 $X = (2, 4, 3, 0)$ 时，$X_1 + X_3 = 5$，$X_1 + X_4 = 2$，$X_2 + X_2 = 8$，因此满足所有条件。此外，$X = (0, 2, 5, 2)$，$X = (1, 3, 4, 1)$ 等也都满足所有条件，输出这些答案也可以。

样例解释 2

不存在满足所有条件的数列 $X$。

由 ChatGPT 4.1 翻译