No.1054 Union add query

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1054 Union add query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 184
作問者 :

QCFium / テスター :

37zigen

42 ProblemId : 3592 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-05-15 21:26:31

問題文

$N$ 頂点 $0$ 辺の無向グラフがあります。各頂点には最初0が書かれています。
以下のクエリを $Q$ 回処理してください。
$i$ 回目のクエリでは $T_{i}, A_{i}, B_{i}$ が与えられます。

$T_{i} = 1$ のとき

A_{i}

B_{i}

$T_{i} = 2$ のとき

A_{i}

A_{i}

B_{i}

$T_{i} = 3$ のとき

A_{i}

入出力の量には注意してください。std::cin/std::coutを使った場合、scanf/printfを使った場合と比べて600ms程度遅くなりました。

入力

 $N Q$ 
 $T_{1} A_{1} B_{1}$ 
 $T_{2} A_{2} B_{2}$ 
 $T_{3} A_{3} B_{3}$ 
 $⋮$ 
 $T_{Q} A_{Q} B_{Q}$

$1 \leq N \leq 5 \times 10^{5}$
$1 \leq Q \leq 5 \times 10^{5}$
$T_{i}$ は $1, 2, 3$ のいずれか

$T_{i} = 1$ のとき : $1 \leq A_{i} \leq N, 1 \leq B_{i} \leq N$
$T_{i} = 2$ のとき : $1 \leq A_{i} \leq N, - 2000 \leq B_{i} \leq 2000$
$T_{i} = 3$ のとき : $1 \leq A_{i} \leq N, B_{i} = 0$

グラフは常に単純
入力は全て整数

出力

$T_{i} = 3$ であるようなクエリ全てに対する答えを一行ずつ出力してください。

サンプル

サンプル1

入力

出力

クエリ1 : 頂点1に書かれている数が0から10になります
クエリ2 : 頂点1に書かれている数は10です
クエリ3 : 頂点1と頂点2を繋ぎます
クエリ4 : 頂点2と連結な頂点1,2に書かれている数が20足されます
クエリ5 : 頂点1と頂点3を繋ぎます
クエリ6 : 頂点2と連結な頂点1,2,3に書かれている数が40足されます
クエリ7 : 頂点1に書かれているのは70です
クエリ8 : 頂点2に書かれているのは60です
クエリ9 : 頂点3に書かれているのは40です

サンプル2

入力

出力

サンプル3

入力

出力

0
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.1054 Union add query

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力