102777: [AtCoder]ABC277 Ex - Constrained Sums
Description
Score : $600$ points
Problem Statement
Determine whether there is a sequence of $N$ integers $X = (X_1, X_2, \ldots ,X_N)$ that satisfies all of the following conditions, and construct one such sequence if it exists.
- $0 \leq X_i \leq M$ for every $1 \leq i \leq N$.
- $L_i \leq X_{A_i} + X_{B_i} \leq R_i$ for every $1 \leq i \leq Q$.
Constraints
- $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$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$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$
Output
If there is an integer sequence that satisfies all of the conditions in the Problem Statement, print the elements $X_1, X_2, \ldots, X_N$ of one such sequence, separated by spaces. Otherwise, print -1
.
Sample Input 1
4 5 3 1 3 5 7 1 4 1 2 2 2 3 8
Sample Output 1
2 4 3 0
For $X = (2,4,3,0)$, we have $X_1 + X_3 = 5$, $X_1 + X_4 = 2$, and $X_2 + X_2 = 8$, so all conditions are satisfied. There are other sequences, such as $X = (0,2,5,2)$ and $X = (1,3,4,1)$, that satisfy all conditions, and those will also be accepted.
Sample Input 2
3 7 3 1 2 3 4 3 1 9 12 2 3 2 4
Sample Output 2
-1
No sequence $X$ satisfies all conditions.
Input
题意翻译
你需要构造一个长度为 $n$ 的序列 $x$,满足下列条件: - $\forall i\in [1,n]$,$0\le x_i\le M$。 - $\forall i\in [1,Q]$,$L_{i}\le x_{a_i}+x_{b_i}\le R_{i}$。Output
问题描述
确定是否存在一个满足以下所有条件的包含$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$。
约束条件
- $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$
- 输入中的所有值都是整数。
输入
输入从标准输入按以下格式给出:
$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
4 5 3 1 3 5 7 1 4 1 2 2 2 3 8
样例输出1
2 4 3 0
对于$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
3 7 3 1 2 3 4 3 1 9 12 2 3 2 4
样例输出2
-1
不存在满足所有条件的序列$X$。