Official

C - FF Editorial by en_translator


Consider maintaining the follow network with a set \(S\). The given query can be rephrased as follows. Initially, \(S=\emptyset\).

  1. Append an ordered pair \((A,B)\) to the set \(S\). That is, let \(S\leftarrow S\cup\{(A,B)\}\).
  2. Remove an ordered pair \((A,B)\) from the set \(S\). That is, let \(S\leftarrow S\setminus\{(A,B)\}\).
  3. Determine if the ordered pairs \((A,B),(B,A)\) are both contained in \(S\).

There are \(N(N-1)\) kinds of ordered pair that may be given from the input, but the size of the set \(S\) is at most \(Q\) throughout the queries, so we can manage \(S\) with a data structure like an associative array to solve the problem.

Even if your library do not allows to use an ordered pair as the key, you may still correspond an ordered pair \((A,B)\) to an integer \(AN+B\) to solve this problem.

The time complexity is \(O(Q\log Q)\) if you use a data structure like a balanced binary search tree as an associative array, or expected \(O(Q)\) time if you use a hash table etc. .

A sample code follows.

#include <iostream>
#include <set>
#include <utility>

int main() {
    using namespace std;

    unsigned N, Q;
    cin >> N >> Q;

    // The set that maintains the follow network
    set<pair<unsigned, unsigned>> follows;

    for (unsigned _{}; _ < Q; ++_) {
        unsigned type, A, B;
        cin >> type >> A >> B;
        if (type == 1)
            // Add the ordered pair (A, B)
            follows.emplace(A, B);
        else if (type == 2)
            // Remove the ordered pair (A, B)
            follows.erase({A, B});
        else
            // Determine if the ordered pairs (A, B) and (B, A) are both contained
            cout << (follows.count({A, B}) && follows.count({B, A}) ? "Yes" : "No") << endl;
    }

    return 0;
}

posted:
last update: