Submission #604393

#	Time	Username	Problem	Language	Result	Execution time	Memory
604393		schiftyfive4	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	0 ms	212 KiB

joitter2

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

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) "MJ >> LAMELO"
#endif

struct dsu {
  vector<int> p, sz;
  dsu(int n) : p(n), sz(n, 1) {
    iota(p.begin(), p.end(), 0);
  }
  int find(int x) {
    while (x != p[x]) x = p[x] = p[p[x]]; // use for path compression
    // while (x != p[x]) x = p[x];
    return x;
  }
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
      // if (sz[x] < sz[y]) {
        // swap(x, y);
      // }
      p[y] = x;
      sz[x] += sz[y];
      return true;
    }
    return false;
  }
  int size(int x) {
    return sz[find(x)];
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  long long ans = 0;
  dsu d(n);
  vector<long long> cnt(n);
  vector<set<int>> g(n);
  vector<set<int>> links(n);
  for (int i = 0; i < n; i++) {
    links[i].insert(i);
  }
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    int pa = d.find(a);
    int pb = d.find(b);
    if (g[b].find(a) != g[b].end()) {
      ans -= cnt[pa];
      ans -= cnt[pb];
      if (links[pa].size() < links[pb].size()) {
        swap(pa, pb);
      }
      links[pa].insert(a);
      links[pa].insert(b);
      for (int i : links[pb]) {
        links[pa].insert(i);
      }
      links[pb].clear();
      d.unite(pa, pb);
      cnt[pa] = (long long) (links[pa].size() - 1) * d.size(pa);
      ans += cnt[pa];
    } else {
      int sz = d.size(pb);
      if (links[pb].find(a) == links[pb].end()) {
        ans += sz;
        cnt[pb] += sz;
        links[pb].insert(a);
      }
    }
    g[a].insert(b);
    cout << ans << '\n';
  }
}

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