Submission #1277441

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

joitter2

#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>

void small_to_large(std::set<int> &a, std::set<int> &b) {
  if (b.size() < a.size()) {
    for (int i : b) {
      a.insert(i);
    }
  } else {
    for (int i : a) {
      b.insert(i);
    }
    std::swap(a, b);
  }
}

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

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

  std::vector<int> par(n);
  std::iota(par.begin(), par.end(), 0);
  std::vector<std::map<int, std::set<int>>> edges(n); // edges[u][v] = size: the number of edges from u to v, contents: the original u's
  std::vector<int64_t> size(n, 1);                    // size[u] = the size of component u
  std::vector<std::set<int>> in(n), out(n);           // in[u] = the set of nodes coming into u
  // out[u] = the set of nodes coming out of u
  int64_t ans = 0;

  auto root = [&](auto &&self, int u) -> int {
    return u == par[u] ? u : par[u] = self(self, par[u]);
  };

  // we assume we're already dealing with roots
  auto merge = [&](auto &&self, int u, int v) {
    if (u == v) {
      return;
    }
    // make sure the latter small to large (part 2) is efficient
    if (in[v].size() > in[u].size()) {
      std::swap(u, v);
    }

    par[v] = u;
    ans -= edges[u][v].size() * size[v] + edges[v][u].size() * size[u]; // remove in between edges
    // correct in[u/v] to exclude in between edges
    for (int i : edges[u][v]) {
      in[v].erase(i);
    }
    for (int i : edges[v][u]) {
      in[u].erase(i);
    }
    // amortised O(m) total ^
    ans -= in[u].size() * size[u] + in[v].size() * size[v];   // remove outer edges
    ans -= size[u] * (size[u] - 1) + size[v] * (size[v] - 1); // remove internal edges

    std::set<int> additional; // additional nodes that lie on the common path that we have to merge
    // both cases: u->node->v and v->node->u
    for (auto &[u, v] : std::array<std::pair<int, int>, 2>{{{u, v}, {v, u}}}) {
      if (out[u].size() < in[v].size()) {
        for (int i : out[u]) {
          if (in[v].contains(i)) {
            additional.insert(root(root, i));
          }
        }
      } else {
        for (int i : in[v]) {
          if (out[u].contains(i)) {
            additional.insert(root(root, i));
          }
        }
      }
    }

    // small to large merging of edges[][] and into[]
    // part 1: edges[v][_] = edges[u][_]
    if (edges[v].size() < edges[u].size()) {
      for (auto &[a, b] : edges[v]) {
        small_to_large(edges[u][a], b);
      }
    } else {
      for (auto &[a, b] : edges[u]) {
        small_to_large(edges[v][a], b);
      }
      std::swap(edges[u], edges[v]);
    }
    // part 2: edges[_][v] = edges[_][u]
    for (int i : in[v]) {
      small_to_large(edges[i][u], edges[i][v]);
      in[u].insert(i);
    }
    // part 3: maintain out[u]
    if (out[v].size() < out[u].size()) {
      for (int i : out[v]) {
        out[u].insert(i);
      }
    } else {
      for (int i : out[u]) {
        out[v].insert(i);
      }
      std::swap(out[u], out[v]);
    }

    size[u] += size[v];
    ans += in[u].size() * size[u] + size[u] * (size[u] - 1); // re add to answer for the updated node

    // finally, merge all additional nodes
    for (int i : additional) {
      self(self, u, i);
    }
  };

  while (m--) {
    int u, v;
    std::cin >> u >> v;
    int u_orig = u - 1, v_orig = v - 1;
    u = root(root, u - 1), v = root(root, v - 1);
    if (u == v or in[v].contains(u_orig)) {
      std::cout << ans << '\n';
      continue;
    }
    edges[u][v].insert(u_orig), in[v].insert(u_orig), out[u].insert(v_orig);
    ans += size[v];
    if (!edges[v][u].empty()) {
      merge(merge, u, v);
    }
    std::cout << ans << '\n';
  }
}

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