問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
あなたは今「PAIZA の村」という、村人と交流しながら生活していくゲームで遊んでいます。
村人は合計で N 人であり、各村人は 1 ~ N で番号付けられています。
このゲームの目的の一つは村の人々と仲良くなることです。
これを示すパラメータとして、各村人と村人の間には「友好度」と呼ばれる非負整数が定められています。
あなたは、この村で同好会グループを作りました。
村人はこの同好会グループに自由に入会でき、自由に退会することもできます。
あなたは、この同好会グループの管理者でもあるので、グループの人気度を常に把握しなければなりません。
グループの人気度は、グループ内の村人とグループ外の村人の間の友好度のうちの、最大の友好度です。
ただし、グループ が 0 人または N 人の場合はそのグループの人気度は 0 であるとします。
同好会の入退会ログが与えられるので、すべてのログが更新された後の全体の人気度を求めてください。
例えば、入力例 1, 2, 3 を説明する図は以下のようになります。
この例では、村人 1 と村人 2 の友好度は 1、村人 1 と村人 3 の友好度は 3、村人 2 と村人 3 の友好度は 0 です。
・ 入力例1: 同好会に村人 1 が入ると、同好会グループ全体の人気度は、「村人 1 と村人 2 の友好度」と「村人 1 と村人 3 の友好度」の最大値なので、3 です。
・ 入力例2: さらに同好会に村人 2 が入ると、同好会グループ全体の人気度は、「村人 1 と村人 3 の友好度」と「村人 2 と村人 3 の友好度」の最大値なので、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 行に出力してください。
・ 出力の最後に改行を入れ、余計な文字、空行を含んではいけません。
全てのテストケースにおいて、以下の条件を満たします。
・ 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)
3 2 1
1 2 1
1 3 3
+ 1
3
3 2 2
1 2 1
1 3 3
+ 1
+ 2
3
3 2 3
1 2 1
1 3 3
+ 1
+ 2
- 1
1
5 4 4
2 5 9
2 4 0
1 5 6
1 4 6
+ 1
- 1
+ 1
+ 5
9