Submission #681788

#	Time	Username	Problem	Language	Result	Execution time	Memory
681788		peijar	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	2094 ms	548672 KiB

joitter2

#include <bits/extc++.h>
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct chash { // large odd number for C
  const uint64_t C = (int)(4e18 * acos(0)) | 71;
  int operator()(int x) const { return __builtin_bswap64(x * C); }
};

using hash_set = __gnu_pbds::gp_hash_table<int, __gnu_pbds::null_type, chash>;
using hash_table = __gnu_pbds::gp_hash_table<int, hash_set, chash>;

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbAretes;
  cin >> nbSommet >> nbAretes;

  vector<hash_table> outEdges(nbSommet), inEdges(nbSommet);
  vector<int> inDeg(nbSommet);
  vector<int> idCC(nbSommet), szCC(nbSommet, 1);
  vector<vector<int>> inCC(nbSommet);
  for (int i = 0; i < nbSommet; ++i)
    inCC[i].push_back(i);
  iota(idCC.begin(), idCC.end(), 0LL);

  int nbFollows = 0;

  for (int iArete = 0; iArete < nbAretes; ++iArete) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    v = idCC[v];
    if (idCC[u] == idCC[v] or
        (inEdges[v].find(idCC[u]) != inEdges[v].end() and
         inEdges[v][idCC[u]].find(u) != inEdges[v][idCC[u]].end())) {
      cout << nbFollows << '\n';
      continue;
    }
    nbFollows += szCC[v];
    inEdges[v][idCC[u]].insert(u);
    outEdges[idCC[u]][v].insert(u);
    inDeg[v]++;
    u = idCC[u];
    queue<pair<int, int>> toMerge;

    if (outEdges[v].find(u) != outEdges[v].end())
      toMerge.emplace(u, v);

    while (!toMerge.empty()) {
      auto [A, B] = toMerge.front();
      toMerge.pop();
      A = idCC[A], B = idCC[B];
      if (A == B)
        continue;
      dbg(A, B);

      if (szCC[A] < szCC[B])
        swap(A, B);

      if (inEdges[A].find(B) != inEdges[A].end()) {
        nbFollows -= szCC[A] * inEdges[A][B].size();
        inDeg[A] -= inEdges[A][B].size();
        inEdges[A].erase(B);
        outEdges[B].erase(A);
      }
      if (outEdges[A].find(B) != outEdges[A].end()) {
        nbFollows -= szCC[B] * outEdges[A][B].size();
        inDeg[B] -= outEdges[A][B].size();
        outEdges[A].erase(B);
        inEdges[B].erase(A);
      }

      nbFollows += 2 * szCC[A] * szCC[B];
      nbFollows -= inDeg[A] * szCC[A] + inDeg[B] * szCC[B];
      for (auto &[cc, s] : inEdges[B]) {
        for (int y : s) {

          outEdges[cc][B].erase(y);

          if (inEdges[A].find(cc) == inEdges[A].end() or
              inEdges[A][cc].find(y) == inEdges[A][cc].end()) {
            inEdges[A][cc].insert(y), inDeg[A]++;
            outEdges[cc][A].insert(y);
          }
        }
        if (outEdges[A].find(cc) != outEdges[A].end())
          toMerge.emplace(A, cc);
      }

      for (auto &[cc, s] : outEdges[B]) {
        for (int y : s) {

          inEdges[cc][B].erase(y);
          inEdges[cc][A].insert(y);
          outEdges[A][cc].insert(y);
        }
        if (inEdges[A].find(cc) != inEdges[A].end())
          toMerge.emplace(A, cc);
      }

      szCC[A] += szCC[B];
      nbFollows += szCC[A] * inDeg[A];
      for (int x : inCC[B])
        inCC[A].push_back(x), idCC[x] = A;
    }
    cout << nbFollows << '\n';
  }
}

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83