問題一覧 > 通常問題

No.1373 Directed Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 131
作問者 : leaf_1415leaf_1415 / テスター : wotsushiwotsushi
15 ProblemId : 5306 / 出題時の順位表
問題文最終更新日: 2021-02-04 03:18:14

問題文

$N$ 個の頂点と $0$ 本の辺からなるグラフがあります。
$N$ 個の頂点をそれぞれ頂点 $1$、頂点 $2$ 、$\ldots$ 、頂点 $N$ と呼びます。
 
また、長さ $N-1$ の正整数の列 $a_1, a_2, \ldots, a_{N-1}$ が与えられます。
あなたは、「操作 $1$ 」から「操作 $N-1$ 」までの $N-1$ 個の操作を、
操作 $1$、操作$2$、$\ldots$、操作 $N-1$ の順番でそれぞれちょうど $1$ 回ずつ行います。
操作 $i$ では、$1 \leq x \leq N - a_i$ を満たす整数 $x$ を選び、頂点 $x$ から頂点 $x+a_i$ に有向辺を張ります。

$N-1$ 個の操作をすべて終えた後のグラフにおいて、どの頂点へも頂点 $1$ から $0$ 本以上の有向辺をたどって到達できるようにしたいです。
これが可能かどうかを判定し、可能な場合はその操作の手順を一つ示してください。

入力

$N$
$a_1\ a_2\ \cdots\ a_{N-1}$

$2 \leq N \leq 10^5$
$1 \leq a_i \leq N-1$
入力はすべて整数

出力

任意の頂点を頂点 $1$ から到達可能にすることができない場合は、$1$ 行目に"NO"を出力してください。
任意の頂点を頂点 $1$ から到達可能にすることができる場合は、$1$ 行目に"YES"を出力し、さらにその操作の手順を $2$ 行目から $N$ 行目で、$N-1$ 行にわたって出力してください。
具体的には、$1 \leq i \leq N-1$ を満たす整数 $i$ について、操作 $i$ で選ぶ整数 $x$ を $i+1$ 行目に出力してください。
答えとなる操作の手順が複数ある場合は、どれを出力しても正解となります。
"YES"/"NO"のどちらを出力した場合にも、出力の最後には改行してください。

サンプル

サンプル1
入力
4
2 1 2
出力
YES
1
1
2

操作 $1$ で頂点 $1$ から頂点 $3$ に有向辺を張り、
操作 $2$ で頂点 $1$ から頂点 $2$ に有向辺を張り、
操作 $3$ で頂点 $2$ から頂点 $4$ に有向辺を張ります。
その結果、すべての頂点が頂点 $1$ から到達可能になります。

サンプル2
入力
4
3 3 3
出力
NO

$3$ 回の操作のどれにおいても、頂点 $1$ から頂点 $4$ に有向辺を張ることしかできないため、
すべての頂点を頂点 $1$ から到達可能にすることはできません。

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