Submission #1036461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036461		juicy	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	457 ms	61264 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

int n, m;
int lab[N];
set<int> s[N];
set<array<int, 2>> t[N];
queue<array<int, 2>> q;

int size(int u) {
  return -lab[u];
}

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

bool check(set<array<int, 2>> &st, int x) {
  auto it = st.lower_bound(array<int, 2>{x});
  return it != st.end() && (*it)[0] == x;
} 

int count(set<array<int, 2>> &st, int x) {
  auto it = st.lower_bound(array<int, 2>{x});
  int cnt = 0;
  for (; it != st.end() && (*it)[0] == x; it = st.erase(it)) {
    ++cnt;
  }
  return cnt;
}

long long res;

void mrg(int u, int v) {
  u = get(u), v = get(v);
  if (u == v) {
    return;
  }
  int cnt = count(t[u], v);
  res -= (long long) cnt * size(u);
  cnt = count(t[v], u);
  res -= (long long) cnt * size(v);
  res += (long long) 2 * size(u) * size(v);
  if (s[u].size() + t[u].size() < s[v].size() + t[v].size()) {
    swap(u, v);
  }
  for (int x : s[v]) {
    if (check(t[u], x)) {
      q.push({x, u});
    }
  }
  for (auto x : t[v]) {
    if (s[u].find(x[0]) != s[u].end()) {
      q.push({x[0], u});
    }
  }
  for (int x : s[v]) {
    s[u].insert(x);
    auto it = t[x].lower_bound(array<int, 2>{v});
    for (; it != t[x].end() && (*it)[0] == v; it = t[x].erase(it)) {
      t[x].insert({u, (*it)[1]});
    }
  }
  cnt = t[u].size();
  for (auto [x, y] : t[v]) {
    if (t[u].insert({x, y}).second) {
      res += size(u);
    } else {
      --cnt;
    }
    s[x].erase(v);
    s[x].insert(u);
  }
  res += (long long) cnt * size(v);
  lab[u] += lab[v];
  lab[v] = u;
}

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

  cin >> n >> m;
  fill(lab + 1, lab + n + 1, -1);
  for (int i = 1; i <= m; ++i) {
    int a, b; cin >> a >> b;
    int u = get(a), v = get(b);
    if (u != v) {
      s[u].insert(v);
      res += t[v].insert({u, a}).second * size(v);
      if (s[v].find(u) != s[v].end()) {
        q.push({u, v});
      }
      for (; q.size(); q.pop()) {
        mrg(q.front()[0], q.front()[1]);
      }
    }
    cout << res << "\n";
  }
  return 0;
}

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