問題一覧 > 通常問題

No.1054 Union add query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 121
作問者 : QCFiumQCFium / テスター : 37zigen37zigen
31 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$
$\hspace{16pt}\vdots$
$T_Q\ A_Q\ B_Q$

$1 \le N \le 5 \times 10^5$
$1 \le Q \le 5 \times 10^5$
$T_i$は$1,2,3$のいずれか

  • $T_i = 1$のとき : $1 \le A_i \le N, 1 \le B_i \le N$
  • $T_i = 2$のとき : $1 \le A_i \le N, -2000 \le B_i \le 2000$
  • $T_i = 3$のとき : $1 \le A_i \le N, B_i = 0$
グラフは常に単純
入力は全て整数

出力

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

サンプル

サンプル1
入力
3 9
2 1 10
3 1 0
1 1 2
2 2 20
1 1 3
2 2 40
3 1 0
3 2 0
3 3 0
出力
10
70
60
40

クエリ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
入力
8 28
2 3 17
2 7 25
1 3 8
2 5 11
1 1 7
2 7 35
3 7 0
3 8 0
1 4 2
2 2 42
2 3 34
3 8 0
3 4 0
3 2 0
1 5 1
1 1 6
1 6 5
2 6 53
1 6 7
1 6 2
2 4 11
3 1 0
1 4 6
3 7 0
1 3 7
2 1 50
3 8 0
3 3 0
出力
60
0
34
42
42
99
124
84
101

サンプル3
入力
1 3
3 1 0
2 1 10
3 1 0
出力
0
10

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