AT_abc277_h.[ABC277Ex] Constrained Sums

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

判断是否存在一个长度为 $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
```
4 5 3
1 3 5 7
1 4 1 2
2 2 3 8
```
输出#1
```
2 4 3 0
```
输入#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 翻译

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

首页