村人の友好関係
(paizaランク S 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
あなたは今「PAIZA の村」という、村人と交流しながら生活していくゲームで遊んでいます。
村人は合計で N 人であり、各村人は 1 ～ N で番号付けられています。
このゲームの目的の一つは村の人々と仲良くなることです。
これを示すパラメータとして、各村人と村人の間には「友好度」と呼ばれる非負整数が定められています。
あなたは、この村で同好会グループを作りました。
村人はこの同好会グループに自由に入会でき、自由に退会することもできます。
あなたは、この同好会グループの管理者でもあるので、グループの人気度を常に把握しなければなりません。
グループの人気度は、グループ内の村人とグループ外の村人の間の友好度のうちの、最大の友好度です。
ただし、グループ が 0 人または N 人の場合はそのグループの人気度は 0 であるとします。
同好会の入退会ログが与えられるので、ログが更新されるごとに同好会グループ全体の人気度を求めてください。
例えば、入力例 1 を説明する図は以下のようになります。
この例では、村人 1 と村人 2 の友好度は 1、村人 1 と村人 3 の友好度は 3、村人 2 と村人 3 の友好度は 0 です。
・ 同好会に村人 1 が入ると、同好会グループ全体の人気度は、「村人 1 と村人 2 の友好度」と「村人 1 と村人 3 の友好度」の最大値なので、3 です。
・ さらに同好会に村人 2 が入ると、同好会グループ全体の人気度は、「村人 1 と村人 3 の友好度」と「村人 2 と村人 3 の友好度」の最大値なので、3 です。
・ 同好会から村人 1 が抜けると、同好会グループ全体の人気度は、「村人 2 と村人 1 の友好度」と「村人 2 と村人 3 の友好度」の最大値なので、1 です。
- 入力される値
-
N M Q
a_1 b_1 f_1
a_2 b_2 f_2
...
a_M b_M f_M
op_1 q_1
op_2 q_2
...
op_Q q_Q
・ 1 行目にそれぞれ村人の人数を表す整数 N、友好関係の数を示す整数 M、ログが更新される回数を表す整数 Q がこの順で半角スペース区切りで与えられます。
・ 続く M 行のうちの i 行目 (1 ≦ i ≦ Q) には村人間の友好度の情報が与えられます。各行は、「村人 a_i と村人 b_i の友好度は f_i である」ということを表します。ただし、入力に現れない村人の間の友好度は 0 です。
・ 続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には同好会に入会、または退会する村人の情報が与えられます。まず同好会に新たにメンバーが増えるのか、減るのかを示す記号 op_i が与えられます。op_i が "+" の場合、同好会に新たに加わる村人がいることを示し、"-" の場合、同好会から抜ける村人がいることを示します。次に入会または退会する村人の番号を表す整数 q_i が与えられます。
・ 入力は合計で M + Q + 1 行となり、入力値最終行の末尾に改行が １ つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
入力の各行で表されるログ変更に対して、同好会グループ全体の人気度を 1 行に出力してください。
・ 出力の最後に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
全てのテストケースにおいて、以下の条件を満たします。
・ 2 ≦ N ≦ 500
・ 1 ≦ M ≦ N*(N-1)/2
・ 1 ≦ Q ≦ 50,000
・ 1 ≦ a_i, b_i ≦ N, a_i < b_i (1 ≦ i ≦ M)
・ 0 ≦ f_i ≦ 1,000,000,000 (1 ≦ i ≦ M)
・ {a_i, b_i} ≠ {a_j, b_j} (1 ≦ i, j ≦ M, i ≠ j)
・ op_i = "+" または op_i = "-" (1 ≦ i ≦ Q)
・ 1 ≦ q_i ≦ N (1 ≦ i ≦ Q)
・ op_i が "+" のとき、同好会に番号が q_i の村人は属していない (1 ≦ i ≦ Q)
・ op_i が "-" のとき、同好会に番号が q_i の村人が属している (1 ≦ i ≦ Q)
- 入力例1
-
3 2 3
1 2 1
1 3 3
+ 1
+ 2
- 1
- 出力例1
-
3
3
1
- 入力例2
-
5 4 4
2 5 9
2 4 0
1 5 6
1 4 6
+ 1
- 1
+ 1
+ 5
- 出力例2
-
6
0
6
9
