結果

問題 No.3390 Public or Private
コンテスト
ユーザー hidehic0
提出日時 2025-11-28 21:52:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 863 ms / 2,000 ms
コード長 3,299 bytes
コンパイル時間 3,381 ms
コンパイル使用メモリ 298,028 KB
実行使用メモリ 73,728 KB
最終ジャッジ日時 2025-11-28 21:53:04
合計ジャッジ時間 22,310 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 "main.cpp"
#include <bits/stdc++.h>
using namespace std;

#line 6 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/alias.hpp"

template <typename T> using VC = std::vector<T>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "/home/hidehic0/src/github.com/hidehic0/library_cpp/templates/macro.hpp"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define all(a) (a).begin(), (a).end()

template <typename T> bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T> bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

inline void input() {}
template <class H, class... T> void input(H &h, T &...t) {
  std::cin >> h;
  input(t...);
}
template <typename T> void input(std::vector<T> &v) {
  for (int i = 0; i < v.size(); i++) {
    std::cin >> v[i];
  }
}

inline void out() { std::cout << "\n"; }
template <class H, class... T> void out(H &h, T &...t) {
  std::cout << h << " ";
  out(t...);
}

template <typename T> void out(std::vector<T> v) {
  for (int i = 0; i < v.size(); i++) {
    std::cout << v[i] << (i + 1 == v.size() ? "\n" : " ");
  }
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
#line 6 "main.cpp"

int main() {
  ll N, M;
  cin >> N >> M;

  map<ll, si> G1,
      G2; // G1: 自分がフォローしているリスト G2: 自分がフォローされているリスト
  ll O = N;               // 公開アカウント数
  map<ll, bool> is_close; // 非公開か
  mii L;                  // 自分がフォローしているなかで公開アカウントの数

  rep(_, M) {
    ll u, v;
    cin >> u >> v;

    G1[u].emplace(v);
    G2[v].emplace(u);
  }

  for (auto [k, l] : G1) {
    L[k] = l.size();
  }

  ll Q;
  cin >> Q;

  while (Q--) {
    ll q, a, b;
    cin >> q >> a >> b;

    if (q == 1) {
      if (G1[a].count(b) == 1) {
        L[a] -= is_close[b] ^ 1;
        G1[a].erase(b);
        G2[b].erase(a);
      } else {
        L[a] += is_close[b] ^ 1;
        G1[a].emplace(b);
        G2[b].emplace(a);
      }
    } else {
      if (is_close[a]) {
        for (ll t : G2[a]) {
          L[t]++;
        }
        O++;
      } else {
        for (ll t : G2[a]) {
          L[t]--;
        }
        O--;
      }

      is_close[a] ^= 1;
    }

    cout << O + G1[a].size() - L[a] - !is_close[a] << "\n";
  }
}
0