103525: [Atcoder]ABC352 F - Estimate Order
Description
Score: $525$ points
Problem Statement
There are $N$ people, numbered $1$ to $N$.
A competition was held among these $N$ people, and they were ranked accordingly. The following information is given about their ranks:
- Each person has a unique rank.
- For each $1 \leq i \leq M$, if person $A_i$ is ranked $x$-th and person $B_i$ is ranked $y$-th, then $x - y = C_i$.
The given input guarantees that there is at least one possible ranking that does not contradict the given information.
Answer $N$ queries. The answer to the $i$-th query is an integer determined as follows:
- If the rank of person $i$ can be uniquely determined, return that rank. Otherwise, return $-1$.
Constraints
- $2 \leq N \leq 16$
- $0 \leq M \leq \frac{N(N - 1)}{2}$
- $1 \leq A_i, B_i \leq N$
- $1 \leq C_i \leq N - 1$
- $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
- There is at least one possible ranking that does not contradict the given information.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$
Output
Print the answers to the $1$-st, $2$-nd, $\ldots$, $N$-th queries in this order, separated by spaces.
Sample Input 1
5 2 2 3 3 5 4 3
Sample Output 1
3 -1 -1 -1 -1
Let $X_i$ be the rank of person $i$. Then, $(X_1, X_2, X_3, X_4, X_5)$ could be $(3, 4, 1, 2, 5)$ or $(3, 5, 2, 1, 4)$.
Therefore, the answer to the $1$-st query is $3$, and the answers to the $2$-nd, $3$-rd, $4$-th, and $5$-th queries are $-1$.
Sample Input 2
3 0
Sample Output 2
-1 -1 -1
Sample Input 3
8 5 6 7 3 8 1 7 4 5 1 7 2 1 6 2 4
Sample Output 3
1 -1 -1 -1 -1 -1 -1 8
Input
Output
问题描述
有 $N$ 个人,编号为 $1$ 到 $N$。
在这 $N$ 个人中举行了一场比赛,并按照比赛成绩进行了排名。关于他们的排名,有以下信息:
- 每个人都有一个唯一的排名。
- 对于每个 $1 \leq i \leq M$,如果编号为 $A_i$ 的人排名为 $x$,编号为 $B_i$ 的人排名为 $y$,则 $x - y = C_i$。
给定的输入保证至少存在一个排名情况,不会与给定信息矛盾。
回答 $N$ 个查询。第 $i$ 个查询的答案是一个整数,确定方式如下:
- 如果编号为 $i$ 的人的排名可以唯一确定,返回该排名。否则,返回 $-1$。
限制条件
- $2 \leq N \leq 16$
- $0 \leq M \leq \frac{N(N - 1)}{2}$
- $1 \leq A_i, B_i \leq N$
- $1 \leq C_i \leq N - 1$
- $(A_i, B_i) \neq (A_j, B_j) (i \neq j)$
- 至少存在一个排名情况,不会与给定信息矛盾。
- 所有输入值都是整数。
输入
输入从标准输入按以下格式给出:
$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$
输出
按顺序打印第 $1$、$2$、$\ldots$、$N$ 个查询的答案,用空格分隔。
样例输入1
5 2 2 3 3 5 4 3
样例输出1
3 -1 -1 -1 -1
设 $X_i$ 为编号为 $i$ 的人的排名。那么,$(X_1, X_2, X_3, X_4, X_5)$ 可能是 $(3, 4, 1, 2, 5)$ 或 $(3, 5, 2, 1, 4)$。
因此,第 $1$ 个查询的答案是 $3$,第 $2$、$3$、$4$ 和 $5$ 个查询的答案是 $-1$。
样例输入2
3 0
样例输出2
-1 -1 -1
样例输入3
8 5 6 7 3 8 1 7 4 5 1 7 2 1 6 2 4
样例输出3
1 -1 -1 -1 -1 -1 -1 8