Submission #1256983

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

joitter2

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

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);

  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)) {
      // 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;
      }
      // std::cout << debug(answer);
      answer -= (ll) gg[ccu].size() * dsu.sz[ccu];
      answer -= (ll) gg[ccv].size() * dsu.sz[ccv];
      // std::cout << debug(answer);
      for (int w : gg[ccv]) {
        // assert(dsu.root(w) != ccu);
        // assert(dsu.root(w) != ccv);
        gg[ccu].insert(w);
      }
      gg[ccv].clear();
      ggc[ccv].clear();

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

      // std::cout << debug(ccu);
      // std::cout << debug(ccv);

      dsu.join(v, u);
      answer += (ll) gg[ccu].size() * dsu.sz[ccu];
    } else {
      if (!gg[ccv].count(u)) {
        gg[ccv].insert(u);
        answer += dsu.sz[ccv];
      }
      ggc[ccv][ccu]++;
    }

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

  }
  
  return 0;
}

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