大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)
翻译中…
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.
翻译中…
样例
Input #1
4 5 3
1 3 5 7
1 4 1 2
2 2 3 8
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.
Input #2
3 7 3
1 2 3 4
3 1 9 12
2 3 2 4
Output #2
-1
No sequence $X$ satisfies all conditions.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。