Submission #1163846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163846		fryingduc	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	7 ms	14476 KiB

joitter2

// https://oj.uz/submission/981972
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m;
long long res;
int lab[maxn];
set<int> comp[maxn];
set<int> g[maxn], rg[maxn];
vector<pair<int, int>> st;

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void add(int u, int v) {
  g[u].insert(v);
  rg[v].insert(u);
  if (g[v].count(u)) {
    st.emplace_back(u, v);
  }
}

void join(int u, int v) {
  u = find(u), v = find(v);
  if (u == v) return;
  auto calc = [&](int x) {
    return (int)comp[x].size() + (int)g[x].size() + (int)rg[x].size();
  };
  if (calc(u) > calc(v)) swap(u, v);
  res += (1ll * -lab[u] * (int)comp[v].size());
  res += (1ll * -lab[v] * (int)comp[u].size());
  for (auto x:comp[v]) {
    if (comp[u].count(x)) {
      res += lab[u] + lab[v];
    } else {
      comp[u].insert(x);
    }
  }  
  for (auto x:g[v]) {
    rg[x].erase(v); add(u, x);
  }
  for (auto x:rg[v]) {
    g[x].erase(v); add(x, u);
  }
  g[u].erase(v); g[v].erase(u);
  rg[u].erase(v); rg[v].erase(u);
  lab[u] += lab[v];
  lab[v] = u;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    lab[i] = -1;
    comp[i].insert(i);
  }
  while (m--) {
    int u, v; cin >> u >> v;
    v = find(v);
    if (find(u) != v and !comp[v].count(u)) {
      comp[v].insert(u);
      res -= lab[v];
      add(find(u), v);
      while (!st.empty()) {
        join(st.back().first, st.back().second);
        st.pop_back();
      }
    }
    cout << res << '\n';
  }
}

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

  solve();

  return 0;
}

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