← 返回题目列表

AtCoder · joisc2022_h

H. 洒水装置

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

スプリンクラー (Sprinkler) - 原题 PDF 第 1 页
原题PDF第1页
スプリンクラー (Sprinkler) - 原题 PDF 第 2 页
原题PDF第2页
スプリンクラー (Sprinkler) - 原题 PDF 第 3 页
原题PDF第3页
スプリンクラー (Sprinkler) - 原题 PDF 第 4 页
原题PDF第4页
スプリンクラー (Sprinkler) - 原题 PDF 第 5 页
原题PDF第5页
スプリンクラー (Sprinkler) - 原题 PDF 第 6 页
原题PDF第6页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 3 – Sprinkler

               スプリンクラー(Sprinkler)



  JOI 君は,長年にわたる家庭菜園の経験を生かしてIOI 農園を運営することを計画している.

  IOI 農園はN 個の土地からなり,1 からN までの番号が付けられている.また,土地と土地の間をつな
ぐN −1 本の道があり,1 からN −1 までの番号が付けられている.道i (1 ≦i ≦N −1) は土地Ai と土地Bi
の間を双方向に結んでいる.どの土地からどの土地へも何本かの道を通ることで移動できる.IOI 農園の各

土地にはスプリンクラーが設置され,その周囲の土地に水を与えることができる.

  JOI 君はIOI 農園でジョイキビを育てる予定である.ジョイキビは水を与えると背丈が急激に変化する不

思議な植物である.その一方でジョイキビはあまり丈夫でなく,背丈がL 以上のジョイキビは先端から長

さL の部分が折れてしまう.JOI 君は,この折れた部分を収穫する.
 はじめに,JOI 君は土地j (1 ≦j ≦N) に背丈がHj のジョイキビを植える.その後Q 日の間,毎日ジョ
イキビの世話をする.k 日目(1 ≦k ≦Q) には,以下のいずれかの行動をする.

    • タイプ1 : 土地Xk のスプリンクラーを使用し,土地Xk から距離Dk 以下の範囲にある土地に水を与
   える.水が与えられた土地に生えているジョイキビは,背丈がWk 倍になる.しかし,背丈がL 以上
   のジョイキビは先端から長さL の部分が折れてしまうので,最終的に,水が与えられる前の背丈がh
   であったジョイキビは,水が与えられた後背丈が「h × Wk をL で割ったあまり」になる.
    • タイプ2 : 土地Xk に生えているジョイキビの背丈を調べる.

 ここで,土地x (1 ≦x ≦N) と土地y (1 ≦y ≦N) の間の距離とは,土地x から土地y へ道をつたって移動

するために通る必要がある道の本数の最小値のことである.

  JOI 君は,ジョイキビが予定通りに育っていることを確認するために,あらかじめタイプ2 の行動で調べ

るジョイキビの背丈を計算しておくことにした.

  IOI 農園の情報とJOI 君の計画の情報が与えられたとき,JOI 君がタイプ2 の行動で調べるジョイキビの

背丈を計算するプログラムを作成せよ.





                    スプリンクラー– 1 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 3 – Sprinkler



入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N L

      A1 B1
      A2 B2
                                 ...

      AN−1 BN−1
     H1
     H2
                                 ...

     HN

    Q

      (Query 1)

      (Query 2)
                                 ...

      (Query Q)

  各(Query k) (1 ≦k ≦Q) にはいくつかの整数が空白区切りで書かれている.そのうち1 個目の整数をTk

とすると,この行の内容は以下のいずれかである.

    • Tk = 1 のとき,この行には続いて3 個の整数Xk, Dk, Wk がこの順に書かれている.これはJOI 君がk
   日目に取る行動がタイプ1 であり,土地Xk から距離Dk 以下の範囲にある土地に水を与え,水が与
   えられた土地に生えているジョイキビの背丈がWk 倍になることを表す.
    • Tk = 2 のとき,この行には続いて1 個の整数Xk が書かれている.これはJOI 君がk 日目に取る行動
   がタイプ2 であり,土地Xk に生えているジョイキビの背丈を調べることを表す.


出力

 タイプ2 の行動,すなわち,Tk = 2 となるk (1 ≦k ≦Q) それぞれに対して,k 日目時点での土地Xk に生

えているジョイキビの背丈を,標準出力に順に改行区切りで出力せよ.





                    スプリンクラー– 2 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 3 – Sprinkler



制約

    • 2 ≦N ≦200 000.
    • 2 ≦L ≦1 000 000 000 (= 109).
    • 1 ≦Ai < Bi ≦N (1 ≦i ≦N −1).
    • どの土地からどの土地へも何本かの道を通ることで移動できる.

    • 0 ≦Hj ≦L −1 (1 ≦j ≦N).
    • 1 ≦Q ≦400 000.
    • Tk は1, 2 のいずれかである(1 ≦k ≦Q).
    • Tk = 1 のとき,1 ≦Xk ≦N,0 ≦Dk ≦40,0 ≦Wk ≦L −1 (1 ≦k ≦Q).
    • Tk = 2 のとき,1 ≦Xk ≦N (1 ≦k ≦Q).


小課題

    1. (3 点) N ≦1 000,Q ≦1 000.
    2. (9 点) Tk = 1 のとき,Dk ≦1 (1 ≦k ≦Q).
    3. (29 点) Tk = 1 のとき,Dk ≦2 (1 ≦k ≦Q).
    4. (12 点) Tk = 1 のとき,Wk = 0 (1 ≦k ≦Q).
    5. (30 点) Tk = 1 のとき,Wk = 2 (1 ≦k ≦Q).
    6. (17 点) 追加の制約はない.





                    スプリンクラー– 3 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 3 – Sprinkler



入出力例

  入力例1              出力例1

   4 7                            4

   1 2                            2

   2 3                            2

   3 4                            1

   1                              1

   1                              4

   1                              4

   1                              2

   11

   1 2 1 2

   1 1 0 2

   2 1

   2 2

   2 3

   2 4

   1 4 10 2

   2 1

   2 2

   2 3

   2 4

 はじめに,JOI 君はすべての土地に背丈が1 のジョイキビを植える.

  1 日目には,JOI 君は土地2 のスプリンクラーを使用し,土地2 から距離1 以下である土地1, 2, 3 に生え

ているジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれぞれ

2, 2, 2, 1 となる.

  2 日目には,JOI 君は土地1 のスプリンクラーを使用し,土地1 から距離0 以下である土地1 に生えて

いるジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれぞれ

4, 2, 2, 1 となる.

  7 日目には,JOI 君は土地4 のスプリンクラーを使用し,土地4 から距離10 以下である土地1, 2, 3, 4 に

生えているジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれ

ぞれ8, 4, 4, 2 となるが,土地1 に生えているジョイキビの背丈が7 以上であるため先端から長さ7 の部分




                    スプリンクラー– 4 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 3 – Sprinkler


が折れて,最終的にそれぞれ1, 4, 4, 2 となる.

 この入力例は小課題1, 5, 6 の制約を満たす.


  入力例2              出力例2

   6 10                           4

   5 6                            1

   1 2                            4

   1 4                            8

   2 6                            2

   3 6

   9

   2

   3

   4

   9

   1

   10

   1 5 1 7

   2 4

   1 4 1 9

   1 5 0 7

   2 1

   1 1 1 3

   1 6 1 4

   2 5

   2 4

   2 3

  1 日目には,JOI 君は土地5 のスプリンクラーを使用し,土地5 から距離1 以下である土地5, 6 に生えて

いるジョイキビの背丈が7 倍になる.その結果,土地5, 6 に生えているジョイキビの背丈はそれぞれ63, 7

となるが,土地5 に生えているジョイキビは背丈が10 未満になるまで先端から長さ10 の部分が折れ続け,

最終的にそれぞれ3, 7 となる.

 この入力例は小課題1, 2, 3, 6 の制約を満たす.





                    スプリンクラー– 5 / 6

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                         Contest 3 – Sprinkler


 入力例3              出力例3

 8 10                           5

 1 3                            0

 3 5                            0

 4 7                            3

 6 7                            0

 4 5                            0

 7 8                            0

 2 4

 5

 8

 6

 4

 6

 2

 9

 3

 11

 1 2 2 0

 2 1

 1 6 1 0

 2 4

 2 6

 1 5 2 0

 2 8

 1 7 2 0

 2 6

 2 7

 2 4

この入力例は小課題1, 3, 4, 6 の制約を満たす.





                   スプリンクラー– 6 / 6