Submission #858710

#	Time	Username	Problem	Language	Result	Execution time	Memory
858710		NeroZein	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	586 ms	64920 KiB

joitter2

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e5 + 5;

long long ans;
set<int> r[N];
int p[N], sz[N];
set<pair<int, int>> in[N], out[N]; 

int get(int x) {
  return p[x] = (p[x] == x ? x : get(p[x])); 
}

void merge(int x, int y) {
  x = get(x), y = get(y);
  if (x == y) {
    return;
  }
  auto f = in[x].lower_bound(make_pair(y, 0));
  while (f != in[x].end() && f->first == y) {
    ans -= sz[x];
    r[x].erase(f->second); 
    out[y].erase(make_pair(x, f->second)); 
    f = in[x].erase(f); 
  }
  f = in[y].lower_bound(make_pair(x, 0)); 
  while (f != in[y].end() && f->first == x) {
    ans -= sz[y];
    r[y].erase(f->second); 
    out[x].erase(make_pair(y, f->second)); 
    f = in[y].erase(f); 
  }
  if (in[x].size() + out[x].size() < in[y].size() + out[y].size()) {
    swap(x, y); 
  }
  ans -= (long long) in[x].size() * sz[x];
  ans -= (long long) in[y].size() * sz[y];
  ans -= (long long) sz[x] * (sz[x] - 1); 
  ans -= (long long) sz[y] * (sz[y] - 1); 
  vector<int> to_merge; 
  for (auto [i, j] : in[y]) {
    out[i].erase({y, j}); 
    out[i].emplace(x, j); 
    if (!in[x].count({i, j})) {
      in[x].emplace(i, j); 
      r[x].insert(j); 
    }
    f = out[x].lower_bound(make_pair(i, 0)); 
    if (f != out[x].end() && f->first == i) {
      to_merge.push_back(i); 
    }
  }
  p[y] = x;
  sz[x] += sz[y];
  ans += (long long) in[x].size() * sz[x];
  ans += (long long) sz[x] * (sz[x] - 1);
  for (auto [i, j] : out[y]) {
    in[i].erase(make_pair(y, j));
    in[i].emplace(x, j); 
    out[x].emplace(i, j); 
    f = in[x].lower_bound(make_pair(i, 0));
    if (f != in[x].end() && f->first == i) {
      to_merge.push_back(i); 
    }
  }
  for (int i : to_merge) {
    merge(x, i); 
  }
}

void add(int x, int y) {
  int px = get(x), py = get(y);
  if (px == py || r[py].count(x)) {
    return;
  }
  ans += sz[py];
  r[py].insert(x);
  in[py].emplace(px, x);
  out[px].emplace(py, x);
  auto f = in[px].lower_bound(make_pair(py, 0)); 
  if (f != in[px].end() && f->first == py) {
    merge(px, py); 
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  iota(p + 1, p + 1 + n, 1); 
  fill(sz + 1, sz + 1 + n, 1); 
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    cout << ans << '\n'; 
  }
  return 0;
}

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