Submission #1257002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257002		LucaLucaM	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	0 ms	328 KiB

joitter2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#include <map>
#include <queue>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

struct DSU {
  std::vector<int> p, sz;

  void init(int n) {
    p.resize(n);
    sz.resize(n);
    for (int i = 0; i < n; i++) {
      p[i] = i;
      sz[i] = 1;
    }
  }

  int root(int u) {
    return p[u] == u? u : p[u] = root(p[u]);
  }
  void join(int u, int v) {
    u = root(u);
    v = root(v);
    if (p[u] != p[v]) {
      // if (sz[u] > sz[v]) {
      //   std::swap(u, v);
      // }
      p[u] = v;
      sz[v] += sz[u];
    }
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;

  std::vector<int> cc(n);

  for (int i = 0; i < n; i++) {
    cc[i] = i;
  }

  ll answer = 0;

  std::vector<std::map<int, int>> ggc(n); // gcc[u] tine toate cc care dau in u (u e radacina unei cc)
  std::vector<std::set<int>> gg(n);

  DSU dsu;
  dsu.init(n);
  
  std::queue<std::pair<int, int>> todo;
  
  auto merge = [&](int u, int v) {
    int ccu = dsu.root(u);
    int ccv = dsu.root(v);
    if (ccu == ccv) {
      return;
    }
    // u il "absoarbe" pe v
    answer += (ll) dsu.sz[ccu] * dsu.sz[ccv] * 2; // adaug in ambele directii
    ggc[ccu].erase(ccv);
    for (const auto &[ccw, f] : ggc[ccv]) {
      ggc[ccu][ccw] += f;
    }
    ggc[ccv].clear();
    
    answer -= (ll) gg[ccu].size() * dsu.sz[ccu];
    answer -= (ll) gg[ccv].size() * dsu.sz[ccv];

    for (int w : gg[ccv]) {
      if (gg[dsu.root(w)].count(ccu)) {
        todo.push({ccu, dsu.root(w)});
      }
      gg[ccu].insert(w);
    }
    for (int w : gg[ccu]) {
      if (gg[dsu.root(w)].count(ccv)) {
        todo.push({ccu, dsu.root(w)});
      }
    }
    gg[ccv].clear();
    ggc[ccv].clear();

    for (int i = 0; i < n; i++) {
      if (dsu.root(i) == ccv) {
        if (gg[ccu].count(i))  {
          gg[ccu].erase(i);
        }
      }
    }

    dsu.join(v, u);
    answer += (ll) gg[ccu].size() * dsu.sz[ccu];
  };

  while (m--) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;

    int ccu = dsu.root(u);
    int ccv = dsu.root(v);

    if (ccu == ccv) {
      std::cout << answer << '\n';
      continue;
    }
    if (ggc[ccu].count(ccv)) {
      todo.push({u, v});
      while (!todo.empty()) {
        auto [x, y] = todo.front();
        todo.pop();
        merge(x, y);
      }

    } else {
      if (!gg[ccv].count(u)) {
        gg[ccv].insert(u);
        answer += dsu.sz[ccv];
      }
      ggc[ccv][ccu]++;
    }

    for (int i = 0; i < n; i++) {
      for (const auto &[j, f] : ggc[i]) {
        assert(!ggc[j].count(i));
      }
    }

    std::cout << answer << '\n';

  }
  
  return 0;
}

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