Submission #1060302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060302		nima_aryan	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	401 ms	50056 KiB

joitter2

/**
 *    author:  NimaAryan
 *    created: 2024-08-15 13:30:23
**/
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")  // don't trust it

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr int N = 1E5;

i64 ans = 0;
vector<set<int>> S(N);  // all vertices in A
vector<set<int>> T(N);  // {x->a | a \in A}
vector<set<int>> G(N);  // {B | a \in A, a->B}
vector<int> par(N, -1);
queue<pair<int, int>> to_merge;

int find(int x) {
  return par[x] == -1 ? x : par[x] = find(par[x]);
}

int size(int A) {
  return S[A].size() + T[A].size() + G[A].size();
}

void unite(int A, int B) {
  A = find(A), B = find(B);

  if (A == B) {
    return;
  }

  if (size(A) < size(B)) {
    swap(A, B);
  }

  ans -= 1LL * S[A].size() * (S[A].size() - 1);
  ans -= 1LL * S[A].size() * T[A].size();
  ans -= 1LL * S[B].size() * (S[B].size() - 1);
  ans -= 1LL * S[B].size() * T[B].size();

  for (int X : G[B]) {
    if (G[X].count(A)) {
      to_merge.emplace(A, X);
    }
  }
  T[A].insert(T[B].begin(), T[B].end());
  for (int b : S[B]) {
    T[A].erase(b);
  }
  for (int x : T[B]) {
    int X = find(x);
    if (X == A) {
      T[A].erase(x);
    } else if (G[A].count(X)) {
      to_merge.emplace(A, X);
    }
    if (X != A) {
      G[X].erase(B);
      G[X].insert(A);
    }
  }
  S[A].insert(S[B].begin(), S[B].end());
  G[A].insert(G[B].begin(), G[B].end());
  G[A].erase(B);
  G[A].erase(A);
  par[B] = A;

  ans += 1LL * S[A].size() * (S[A].size() - 1);
  ans += 1LL * S[A].size() * T[A].size();

  S[B].clear();
  T[B].clear();
  G[B].clear();
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  for (int x = 0; x < n; ++x) {
    S[x] = {x};
  }

  while (m--) {
    int a, b;
    cin >> a >> b;
    --a, --b;

    int A = find(a), B = find(b);
    if (A != B) {
      if (G[B].count(A)) {
        unite(A, B);
      } else if (!T[B].count(a)) {
        ans += S[B].size();
        T[B].insert(a);
        G[A].insert(B);
      }
      while (!to_merge.empty()) {
        auto [X, Y] = to_merge.front();
        to_merge.pop();
        unite(X, Y);
      }
    }

    cout << ans << "\n";
  }

  return 0;
}

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