問題一覧 > 教育的問題

No.3580 Sum of Two Components

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 14
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10019 / 自分の提出
問題文最終更新日: 2026-07-03 11:29:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

Problem Statement

First, $3$ positive integers $N, M, B$ are given.

 

You are given $M$ conditions, each expressed in the following form using integers $i,j,c$ satisfying $1 \leq i,j \leq N$ and $0 \leq c < B$:

  • $X_i + X_j \equiv c \pmod{B}$.

Determine whether there exists a sequence $X$ of non-negative integers of length $N$, with each element less than $B$, that satisfies all $M$ conditions, and if one exists, find $1$ such sequence.

Here, for each positive integer $i$ not exceeding $N$, $X_i$ denotes the $i$-th element of $X$.

Input

For each positive integer $m$ not exceeding $M$, let $i_m,j_m,c_m$ denote the integers $i,j,c$ appearing in the $m$-th condition.

The input is given from standard input in $1 + M$ lines in the following format:

  • Line $1$ contains $N, M, B$, separated by single-byte spaces.
  • For each positive integer $m$ not exceeding $M$, line $1 + m$ contains $i_m,j_m,c_m$, separated by single-byte spaces.
$N$ $M$ $B$
$i_1$ $j_1$ $c_1$
$\vdots$
$i_M$ $j_M$ $c_M$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 10^3$.
  • $M$ is an integer satisfying $1 \leq M \leq 10^3$.
  • $B$ is an integer satisfying $1 \leq B \leq 10^3$.
  • For every positive integer $m$ not exceeding $M$:
    • $i_m$ is an integer satisfying $1 \leq i_m \leq N$.
    • $j_m$ is an integer satisfying $1 \leq j_m \leq N$.
    • $c_m$ is an integer satisfying $0 \leq c_m < B$.

Output

If no $X$ satisfying the conditions exists, print No.

No

If one exists, find $1$ such $X$, print Yes on line $1$, and on line $2$ print $X_i$ for each positive integer $i$ not exceeding $N$, in ascending order of $i$, separated by single-byte spaces.

Yes
$X_1$ $\cdots$ $X_N$

Print a newline at the end.

This problem uses a special judge. If there are multiple correct answers, you may print any of them.

However, your output must strictly follow the format described above. For example, the behavior of the judge is not guaranteed if there is extra whitespace.

Sample

Sample 1
Input
1 1 1
1 1 0
Output
Yes
0

The conditions that the integer sequence $X = (X_1)$ of length $N = 1$ must satisfy are

$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 1 \\ X_1 & + & X_1 & \equiv & 0 \pmod {1} \end{array} \right. $

. $X = (0)$ indeed satisfies all of these conditions.

Sample 2
Input
1 1 2
1 1 1
Output
No

The conditions that the integer sequence $X = (X_1)$ of length $N = 1$ must satisfy are

$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 2 \\ X_1 & + & X_1 & \equiv & 1 \pmod {2} \end{array} \right. $

. No $X$ satisfies all of these conditions.

Sample 3
Input
2 1 3
1 2 0
Output
Yes
0 0

The conditions that the integer sequence $X = (X_1,X_2)$ of length $N = 2$ must satisfy are

$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 3 \\ 0 & \leq & X_2 & < & 3 \\ X_1 & + & X_2 & \equiv & 0 \pmod {3} \end{array} \right. $

. $X = (0,0)$ indeed satisfies all of these conditions. Besides this,

Yes
1 2

and others are also accepted as correct.

Sample 4
Input
2 2 4
1 2 0
1 2 1
Output
No

The conditions that the integer sequence $X = (X_1,X_2)$ of length $N = 2$ must satisfy are

$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 4 \\ 0 & \leq & X_2 & < & 4 \\ X_1 & + & X_2 & \equiv & 0 \pmod {4} \\ X_1 & + & X_2 & \equiv & 1 \pmod {4} \end{array} \right. $

. No $X$ satisfies all of these conditions.

Sample 5
Input
3 3 5
1 2 1
2 3 3
3 1 4
Output
Yes
1 0 3

The conditions that the integer sequence $X = (X_1,X_2,X_3)$ of length $N = 3$ must satisfy are

$\displaystyle \left\{ \begin{array}{ccccl} 0 & \leq & X_1 & < & 5 \\ 0 & \leq & X_2 & < & 5 \\ 0 & \leq & X_3 & < & 5 \\ X_1 & + & X_2 & \equiv & 1 \pmod {5} \\ X_2 & + & X_3 & \equiv & 3 \pmod {5} \\ X_3 & + & X_1 & \equiv & 4 \pmod {5} \end{array} \right. $

. $X = (1,0,3)$ indeed satisfies all of these conditions.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。