← 返回题目列表

AtCoder · joisc2018_a

A. 公路建设

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

高速道路の建設 (Construction of Highway) - 原题 PDF 第 1 页
原题PDF第1页
高速道路の建設 (Construction of Highway) - 原题 PDF 第 2 页
原题PDF第2页
高速道路の建設 (Construction of Highway) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                           Contest Day 1 – Construction of Highway


            高速道路の建設(Construction of Highway)



  JOI 王国にはN 個の都市があり,1 からN までの番号が付けられている.都市1 は首都である.各都市
には活気と呼ばれる値が存在し,都市i (1 ≦i ≦N) の活気の初期値はCi である.
  JOI 王国の道路は,2 つの異なる都市を双方向に結ぶ.JOI 王国にははじめ,道路は存在しない.JOI 王
国はこれからN −1 本の道路からなる道路網の建設を行う.j 回目(1 ≦j ≦N −1) の道路の建設は以下の
ようにして行われる.

   • 都市A j と都市Bj が指定される.このとき,都市1 から幾つかのその時点で建設されている道路を
   経由することで,都市A j へは到達可能であり,都市Bj へは到達可能でない.

   • 都市A j と都市Bj を結ぶ道路を建設する.このとき,以下の条件を満たす都市の組(s, t) の数だけコ
   ストがかかる.

     都市s と都市t は都市1 と都市A j を結ぶ最短のパス上に存在し,都市1 から都市A j に行
     く際に都市s に都市t より先に到達し,都市s の活気の値が都市t の活気の値より真に大
     きい.

   ここで,都市1 と都市A j を結ぶパス上の都市には,都市1 と都市A j 自身も含むとする.なお,都
   市1 と都市A j を結ぶ最短のパスは,ただ1 つ存在することに注意せよ.

   • 都市1 と都市A j を結ぶ最短のパス上に存在するすべての都市について,その活気の値が都市Bj の
   活気の値に変化する.

 それぞれの道路の建設にかかるコストを知りたい.


課題

 都市と道路の建設計画の情報が与えられたとき,それぞれの道路の建設にかかるコストを求めるプログ
ラムを作成せよ.


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N が書かれている.これはJOI 国にN 個の都市が存在することを表す.

   • 2 行目にはN 個の整数C1,C2, · · · ,CN が空白を区切りとして書かれている.これらは都市i(1 ≦i ≦N)
   の活気の初期値がCi であることを表す.

   • 続くN −1 行のうちのj 行目(1 ≦j ≦N −1)には2 個の整数A j, Bj が空白を区切りとして書かれ
   ている.これらはj 回目の道路の建設において都市A j と都市Bj が指定されることを表す.



                    高速道路の建設– 1 / 3

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                           Contest Day 1 – Construction of Highway


出力

 標準出力にN −1 行で出力せよ.N −1 行のうちのj 行目(1 ≦j ≦N −1) には,j 回目の道路の建設にか
かるコストを出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 1 ≦N ≦100 000.

   • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N).

   • 1 ≦A j ≦N (1 ≦j ≦N −1).

   • 1 ≦Bj ≦N (1 ≦j ≦N −1).

   •  j 回目より前に建設された道路を用いて,都市1 から都市Aj へは到達可能であり,都市Bj へは到
   達可能でない(1 ≦j ≦N −1).


小課題

 この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.


小課題1 [7 点]

   • N ≦500.


小課題2 [9 点]

   • N ≦4000.


小課題3 [84 点]

 追加の制限はない.





                    高速道路の建設– 2 / 3

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                           Contest Day 1 – Construction of Highway


入出力例

  入力例1        出力例1
   5                    0
   1 2 3 4 5            0
   1 2                  0
   2 3                  2
   2 4
   3 5

 入力例1 では,以下のように建設が行われる.

   • 1 回目の建設では条件を満たす都市s, 都市t の組は存在しないので建設にかかるコストは0 である.
   都市1 と都市2 の間に道路ができ,都市1 の活気の値が2 に変わる.

   • 2 回目の建設でも建設にかかるコストは0 である.都市2 と都市3 の間に道路ができ,都市1 と都市
     2 の活気の値が3 に変わる.

   • 3 回目の建設でも建設にかかるコストは0 である.都市2 と都市4 の間に道路ができ,都市1 と都市
     2 の活気の値が4 に変わる.

   • 4 回目の建設では(s, t) = (1, 3), (2, 3) が条件をみたすので建設にかかるコストは2 である.都市3 と
   都市5 の間に道路ができ,都市1 と都市2 と都市3 の活気の値が5 に変わる.


  入力例2              出力例2
   10                             0
   1 7 3 4 8 6 2 9 10 5           0
   1 2                            0
   1 3                            1
   2 4                            1
   3 5                            0
   2 6                            1
   3 7                            2
   4 8                            3
   5 9
   6 10





                    高速道路の建設– 3 / 3