問題一覧 > 通常問題

No.1216 灯籠流し/Lanterns

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : kaagekaage / テスター : autumn-eelautumn-eel
2 ProblemId : 4852 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-30 15:15:33

問題文

Paken River では、技術室奥プログラミングコンテスト#5 の開催を記念し、このコンテストの末長い存続を願って、 灯籠流しが行われることになりました。
Paken River には N 個の「チェックポイント」があり、1 から N までの番号がつけられています。
チェックポイント AiBi は、他のチェックポイントを経由せずに川でつながっており、この間を灯籠は時間 Ci かけて流れます。
また、チェックポイント 1 は、Paken River の河口であり、川はここへ向かって流れます。
さらに、すべてのチェックポイントは川を通してつながっており、 川が、流れる方向に向かって枝分かれすることはありません。
つまり、川は、チェックポイントを頂点とし、河口を根とした根付き木の形状をしています。
灯籠は、あるチェックポイントから流されると、川の流れに沿って進んでいき、流されてから、灯籠ごとに定められている時間が経つと消灯します。
最初の計画では、川にひとつも灯籠は流されません。次の Q 個のクエリに答えてください。

  • 追加クエリ: チェックポイント vi から時刻 ti に流す灯籠を追加する。この灯籠は li 単位時間経つと消灯する。
  • 回答クエリ: チェックポイント vi で時刻 ti までに点灯した状態で見られる灯籠の総数を出力する。ただし、時刻 ti ちょうどに見られる場合・vi から流す場合・vi に到達したときにちょうど消える場合(14:36 追記)も含める。このクエリでは必ず li=0 である。

入力

N Q
A1 B1 C1
A2 B2 C2

AN1 BN1 CN1
type1 v1 t1 l1
type2 v2 t2 l2

typeQ vQ tQ lQ

typei=0 のとき追加クエリ、typei=1 のとき回答クエリを表します。

  • 2N50000
  • 1Q100000
  • 1Ai,Bi,viN
  • 0Ci,ti,li1012
  • typei=0,1
  • typei=1 なら li=0
  • 与えられるグラフは木
  • 入力は全て整数

出力

すべての回答クエリについて、チェックポイント vi で時刻 ti までに点灯した状態で見られる灯籠の総数をそれぞれ1行に出力してください。

小課題

実際に点数が与えられることはありませんが、この問題には、100点満点とした場合の複数の小課題が用意されています。
考察の助けや、コンテスト後の感想戦にご活用ください。なお、これらの制約を満たすテストケースの存在は保証されていません。(15:15 追記)

小課題1 (1点)

  • N,Q300

小課題2 (15点)

  • Ci106, typei=0 なら ti106, typei=1 なら ti=1012

小課題3 (27点)

  • N,Q2000

小課題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もしくは右上の雲マークをクリックしてアカウントを作成してください。