← 返回题目列表

AtCoder · joisc2010_highway

highway. 高速公路

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

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

高速道路 (Highway) - 原题 PDF 第 1 页
原题PDF第4页
高速道路 (Highway) - 原题 PDF 第 2 页
原题PDF第5页
高速道路 (Highway) - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                          Contest day 4 - Highway

                    高速道路(Highway)


 カナダには,都市1 から都市N までのN 個の都市と,高速道路1 から高速道路N −1 までのN −1 本の
高速道路がある.すべての高速道路は2 つの都市を結んでおり,どちらの方向にも通ることができる.さ
らにこの高速道路網は,どの2 つの都市もいくつかの高速道路を乗り継ぐことで行き来できるように設計
されている.言い換えると,N 個の都市とN −1 本の高速道路は木構造をなしている.
 渋滞情報センターの施設長に任命されたあなたは,この高速道路網の渋滞情報を管理しなければならない.
 この施設では,N −1 本それぞれの高速道路について,その始点の都市から終点の都市までの所要時間の
データを管理している.たとえば下図のように都市1 と都市3,都市3 と都市4,都市2 と都市3 が高速道
路で繋がっている状況の場合,(i, j) = (1, 3), (3, 1), (3, 4), (4, 3), (2, 3), (3, 2) のそれぞれについて「都市i から
都市j への所要時間」をこの施設で管理している(高速道路は上りと下りで所要時間が同じとは限らないこ
とに注意せよ).





 それに加えて,この施設では次の2 つのことを行う.
 まず,この施設には時おり「渋滞情報」が入ってくる.1 回の渋滞情報は3 つの正の整数r, s, t によって
与えられる.これは「高速道路r の上りの所要時間がs ,下りの所要時間がt である」ことを表す.ただ
し高速道路の上りとは,その高速道路の始点と終点の都市のうち番号が小さいほうの都市から大きいほう
への都市へと向かう方向を指し,下りとはその逆方向を指すものとする.この渋滞情報に従って,施設の
データを更新する.
 また,この施設には「問い合わせ」の電話がかかってくることがある.1 回の問い合わせは2 つの正の整
数x, y によって与えられる.このとき,施設で管理している現在のデータをもとに「都市x から都市y へ
の所要時間」を計算して答えなければならない.

課題(TASK)
 ある1 日の間の「渋滞情報」と「問い合わせ」(これらをまとめてクエリという) の列が時刻順に与えたと
き,それぞれの問い合わせごとに,その問い合わせの答えを出力するプログラムを作成せよ.ただし,最
初の渋滞情報が入ってくる前の段階では,N −1 本すべての高速道路の所要時間は上下線ともに1 である.





                                                                                    Page 1 of 3

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                          Contest day 4 - Highway

制限(CONSTRAINTS)
   2 ≦N ≦100, 000 都市の数
   1 ≦M ≦100, 000 渋滞情報の数と問い合わせの数の和

入力(INPUT)

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

   • 1 行目には整数N とM が空白を区切りとして書かれている.

   • 続くN −1 行は,1 行につき1 本の高速道路について記述している.これらの行のi 行目には2 つの
    整数pi, qi (1 ≦pi < qi ≦N) が空白を区切りとして書かれており,これは高速道路i が都市pi と都市
       qi を結んでいることを表す.

   • 続くM 行は,1 行につき1 つのクエリ(渋滞情報または問い合わせ) について記述しており.次のど
   ちらか一方が書いてある:

       – 渋滞情報· · · 1 文字‘I’ と,整数r (1 ≦r ≦N −1), s (1 ≦s ≦1, 000), t (1 ≦t ≦1, 000).それぞれ
     は空白を区切りとして与えられる.
       – 問い合わせ· · · 1 文字‘Q’ と,異なる2 つの整数x (1 ≦x ≦N), y (1 ≦y ≦N).それぞれは空白
     を区切りとして与えられる.

出力(OUTPUT)

 標準出力に以下のデータを出力せよ.

   • 出力するデータの行数は入力中に現れる文字‘Q’ の個数である.i 行目は,第i 番目の問い合わせの
   答えを表す1 つの整数を含む.

採点基準(GRADING)
  20 点分のテストグループにおいて,N, M は1, 000 を超えない.また,50 点分のテストグループにおい
て,任意の都市から別の任意の都市へ必ず1, 000 本以下の高速道路を乗り継いで移動することができる.





                                                                                    Page 2 of 3

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                          Contest day 4 - Highway

入出力例(EXAMPLE)
  入力例(Sample Input)  出力例(Sample Output)
   4 5                 2
   1 3                 13
   3 4                 12
   2 3
   I 1 7 9
   Q 2 4
   I 3 12 11
   Q 2 4
   Q 4 2





                                                                                    Page 3 of 3