제출 #1277598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277598		avighna	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++20	100 / 100	596 ms	59944 KiB

joitter2

#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

class joitter_dsu {
private:
  int n;
  std::vector<int> par;
  std::vector<int64_t> size;

  std::vector<std::set<int>> in, comps_in;        // in[u]  = set of original nodes going into comp u
                                                  // comps_in[u] = instead of the original nodes we store components
  std::vector<std::set<std::pair<int, int>>> out; // out[u] = set of {u_orig, v} edges coming out of comp u
  std::queue<std::pair<int, int>> join_queue;

  int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }

  void merge(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return;
    }
    par[v] = u;
    size[u] += size[v];
  }

  void erase_edge(int u_orig, int v_orig) {
    int u = root(u_orig), v = root(v_orig);
    in[v].erase(u_orig);
    out[u].erase({u_orig, v});
  }

  bool insert_edge(int u_orig, int v_orig) {
    int u = root(u_orig), v = root(v_orig);
    if (u == v or in[v].contains(u_orig)) {
      return false;
    }
    out[u].insert({u_orig, v});
    in[v].insert(u_orig);
    comps_in[v].insert(u);
    if (comps_in[u].contains(v)) {
      join_queue.push({u, v});
    }
    return true;
  }

  void join(int u, int v) {
    u = root(u), v = root(v);
    if (u == v) {
      return;
    }
    if (in[v].size() + out[v].size() > in[u].size() + out[u].size()) {
      std::swap(u, v);
    }
    ans -= in[u].size() * size[u] + size[u] * (size[u] - 1);
    ans -= in[v].size() * size[v] + size[v] * (size[v] - 1);
    std::vector<std::pair<int, int>> insert, erase;
    for (auto &[x, y] : out[v]) {
      erase.push_back({x, y});
      if (y != u) { // exclude internal edges
        insert.push_back({x, y});
      }
    }
    for (const int &i : in[v]) {
      erase.push_back({i, v});
      if (root(i) != u) { // same as above
        insert.push_back({i, v});
      }
    }
    for (auto &[x, y] : erase) {
      erase_edge(x, y);
    }
    merge(u, v);
    for (auto &[x, y] : insert) {
      insert_edge(x, y);
    }
    ans += in[u].size() * size[u] + size[u] * (size[u] - 1);
  }

public:
  int64_t ans;

  joitter_dsu(int n) : n(n), par(n), size(n, 1), in(n), comps_in(n), out(n), ans(0) {
    std::iota(par.begin(), par.end(), 0);
  }

  void add(int u, int v) {
    if (!insert_edge(u, v)) {
      return;
    }
    ans += size[root(v)];
    while (!join_queue.empty()) {
      auto [x, y] = join_queue.front();
      join_queue.pop();
      join(x, y);
    }
  }
};

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

  int n, m;
  std::cin >> n >> m;
  joitter_dsu dsu(n);
  for (int i = 0, u, v; i < m; ++i) {
    std::cin >> u >> v;
    dsu.add(u - 1, v - 1);
    std::cout << dsu.ans << '\n';
  }
}

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