No.1216 灯籠流し/Lanterns
タグ : / 解いたユーザー数 15
作問者 : kaage / テスター : autumn-eel
問題文
Paken River では、技術室奥プログラミングコンテスト#5 の開催を記念し、このコンテストの末長い存続を願って、
灯籠流しが行われることになりました。
Paken River には
チェックポイント
また、チェックポイント
さらに、すべてのチェックポイントは川を通してつながっており、
川が、流れる方向に向かって枝分かれすることはありません。
つまり、川は、チェックポイントを頂点とし、河口を根とした根付き木の形状をしています。
灯籠は、あるチェックポイントから流されると、川の流れに沿って進んでいき、流されてから、灯籠ごとに定められている時間が経つと消灯します。
最初の計画では、川にひとつも灯籠は流されません。次の
- 追加クエリ: チェックポイント
から時刻 に流す灯籠を追加する。この灯籠は 単位時間経つと消灯する。 - 回答クエリ: チェックポイント
で時刻 までに点灯した状態で見られる灯籠の総数を出力する。ただし、時刻 ちょうどに見られる場合・ から流す場合・ に到達したときにちょうど消える場合(14:36 追記)も含める。このクエリでは必ず である。
入力
なら- 与えられるグラフは木
- 入力は全て整数
出力
すべての回答クエリについて、チェックポイント
小課題
実際に点数が与えられることはありませんが、この問題には、100点満点とした場合の複数の小課題が用意されています。
考察の助けや、コンテスト後の感想戦にご活用ください。なお、これらの制約を満たすテストケースの存在は保証されていません。(15:15 追記)
小課題1 (1点)
小課題2 (15点)
, なら , なら
小課題3 (27点)
小課題4 (57点)
- 追加の制約はない。
サンプル
サンプル1
入力
3 4
1 2 5
3 1 3
0 2 1 5
0 3 0 4
1 1 5 0
1 1 6 0
出力
1
2
頂点 2 から流された灯籠は時刻 6 に、3 から流された灯籠は時刻 5 に、点灯したまま頂点 1 にたどりつきます。
サンプル2
入力
7 9
1 6 4
5 7 1
5 1 7
3 2 4
2 4 3
1 2 5
0 3 1 5
0 4 0 8
0 7 4 2
1 1 7 0
1 1 10 0
0 6 5 5
1 2 7 0
0 4 1 5
1 2 8 0
出力
0
1
2
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。