Submission #1234437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234437		elvinoo	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	100 / 100	524 ms	65268 KiB

joitter2

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
#define int long long
#define f first
#define s second
using namespace std;

int mod = 1e9 + 7;

int ans = 0;
queue<pair<int, int>> q;
vector<set<int>> t, f, c;

struct DSU {
  vector<int> e;
  DSU(int N) {e = vector<int>(N, -1);}

  int get(int x) {return e[x] < 0 ? x : e[x] = get(e[x]);}

  bool same_set(int a, int b) {return get(a) == get(b);}

  int size(int x) {
    x = get(x);
    return c[x].size() + t[x].size() + f[x].size();
  }

  int dsu_size(int x) {
    x = get(x);
    return -e[x];
  }

  void erase(int x, int y) {
    t[x].erase(y);
    t[y].erase(x);
    f[x].erase(y);
    f[y].erase(x);
  }

  void insert(int x, int y) {
    t[x].insert(y);
    f[y].insert(x);

    if (t[y].count(x)) q.push({x, y});
  }

  void unite(int x, int y) {
    x = get(x);
    y = get(y);
    
    if (x == y) return;
    if (size(x) < size(y)) swap(x,y);

    ans += c[x].size() * (-e[y]) + c[y].size() * (-e[x]);

    e[x] += e[y];
    e[y] = x;

    erase(x, y);

    for (int i : c[y]) {
      if (c[x].count(i)) ans += e[x];
      else c[x].insert(i);
    }

    for (int i : t[y]) {
      f[i].erase(y);
      insert(x, i);
    }

    for (int i : f[y]) {
      t[i].erase(y);
      insert(i, x);
    }
  }
};

void solve() {
  int n, m;
  cin >> n >> m;

  t.resize(n + 1);
  f.resize(n + 1);
  c.resize(n + 1);

  for (int i = 1; i <= n; i++) c[i].insert(i);
  DSU dsu(n + 1);

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

    b = dsu.get(b);
    if (dsu.get(a) != b && !c[b].count(a)) {
      c[b].insert(a);
      ans += dsu.dsu_size(b);

      a = dsu.get(a);
      dsu.insert(a, b);

      while (!q.empty()) {
        pair<int, int> k = q.front();
        q.pop();
        dsu.unite(k.f, k.s);
      }
    }

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

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

  solve();
  return 0;
}

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