AtCoder Beginner Contest 278 C問題 FF
問題
提出解答
問題の概要
SNS Twidai には 人のユーザーがおり, ユーザー
ユーザー
と名付けられている. 最初, どのユーザーも他のユーザーをフォローしていない.
次の 個の履歴及び質問に答えよ.
: ユーザー
がユーザー
をフォローする. ただし, 既にフォローしている場合は何も起こらない.
: ユーザー
がユーザー
のフォローを解除する. ただし, 既にフォローしていない場合は何も起こらない.
: ユーザー
とユーザー
が互いにフォローしあっているか? 答えよ.
制約
となる
が存在する.
解法
が非常に小さい場合は
でユーザー
がユーザー
をフォローしているかどうかを表している整数を用意することで処理できる. ただし, これは計算量として
時間を要してしまう.
個の集合
を用意し, 次のようにして処理できる. これらは最初空集合である.
:
に
を加える.
:
から
を削除する.
:
かつ
かどうかを判定する.
集合によって各クエリを や
時間で処理できる. ただし,
が非常に大きいので, 全てを用意することはできない. そこで, map (C++) や defaultdict (Python) を利用し, 必要になった瞬間に空集合を用意することによって, 多くても
個の集合を用意することで済む.
このような工夫によって 時間や
時間で処理できる.