No.2294 Union Path Query (Easy)
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 :
t98slider
/ テスター :
akakimidori
タグ : / 解いたユーザー数 27
作問者 :

問題文最終更新日: 2023-05-11 02:56:26
問題文
頂点 辺の重み付き無向グラフ と 変数 があります。グラフの頂点にはそれぞれ から までの番号付けがされています。
変数 ははじめ で初期化されています。
グラフ における2頂点間 , の距離 を次のように定義します。
同一頂点での距離は とします。
以下のような 個のクエリが与えられるので、グラフ と変数 に対して順に処理してください。
1 v w
:頂点 と頂点 を重み の辺で結ぶ。与えられる入力ではこの操作によってグラフ に閉路ができないことが保証される。2 u v
:頂点 と頂点 が連結でない場合-1
を出力する。連結である場合、 を出力し、 に を加算する。
その後、 を で割ったあまりとする。3 v
:頂点 と同一の連結成分に含まれるすべての頂点対についての距離の総和を で割ったあまりを出力する。
すなわち、頂点 と連結である頂点 (頂点 も含む)が 個あるとし、それぞれ とした際の を出力する。頂点 と連結である頂点が つしかない (頂点 のみである) 場合、0
を出力する。4 value
: に値 を加算する。その後、 を で割ったあまりとする。
入力
- について
タイプ1のクエリのときタイプ2のクエリのとき
タイプ3のクエリのとき
タイプ4のクエリのとき
・
・
・タイプ1のクエリによってグラフ に閉路ができないことが保証される。 - 入力はすべて整数
出力
タイプ2、タイプ3のクエリが合計で 個与えられるとして、 行目にそれぞれのクエリの回答を1行に出力してください。最後に改行してください。
サンプル
サンプル1
入力
5 1 11 1 0 1 2 0 1 2 0 2 1 0 2 3 1 4 4 1 3 5 3 3 2 3 2 1 4 11 3 3
出力
1 -1 6 21 6 62
サンプル1の説明を見る (クリックで展開します)

初期状態では、 頂点 辺のグラフとなっています。変数は に初期化されています。
1 0 1
:1つ目のクエリでは、頂点 と頂点 を重み の辺で結びます。2 0 1
:2つ目のクエリでは、頂点 と頂点 の距離 を出力します。変数 に を加算し、 で割ったあまりとします。これによって変数 は となります。2 0 2
:3つ目のクエリでは、頂点 と頂点 は非連結ですので、 を出力します1 0 2
:4つ目のクエリでは、頂点 と頂点 を重み の辺で結びます。3 1
:5つ目のクエリでは、頂点 の所属する連結成分についての頂点対の距離の総和が求められます。
ですので、これらの総和である を出力します。4 4
:6つ目のクエリでは、変数 に を加算し、 で割った余りとします。これによって変数 は となります。1 3 5
:7つ目のクエリでは、頂点 と頂点 を重み の辺で結びます。3 3
:8つ目のクエリでは、頂点 の所属する連結成分についての頂点対の距離の総和が求められます。
ですので、これらの総和である を出力します。2 3 2
:9つ目のクエリでは、頂点 と頂点 の距離 を出力します。変数 に を加算し、 で割ったあまりとします。これによって変数 は となります。1 4 11
:10個目のクエリでは、頂点 と頂点 を重み の辺で結びます。3 3
:11個目のクエリでは、頂点 の所属する連結成分についての頂点対の距離の総和が求められます。
ですので、これらの総和である を出力します。
サンプル2
入力
7 5 15 2 0 5 1 1 542099847 1 0 126014135 2 6 1 1 3 606571677 1 4 630122460 3 2 2 5 3 2 6 6 1 2 660183552 3 3 2 1 3 2 5 1 2 5 2 3 1
出力
-1 -1 0 606571677 0 995222351 73942298 542099847 58594973 995222351
サンプル3
入力
8 3 10 2 6 2 1 1 789992496 1 4 345094264 1 2 654214606 1 5 184875134 3 1 1 7 378850180 1 0 389600407 3 0 2 2 3
出力
-1 900591855 327463395 654214606
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。