제출 #1277409

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

joitter2

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

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, int>> edges(n); // edges[u][v] = the number of edges from u to v
  std::vector<int64_t> in(n), size(n, 1);   // in[u] = the number of edges in total into u
  // size[u] = the size of component u
  std::vector<std::set<int>> into(n), outof(n); // into[u] = the set of nodes coming into u
  // outof[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 that are not equal
  auto merge = [&](auto &&self, int u, int v) {
    if (u == v) {
      return;
    }
    // make sure the latter small to large (part 2) is efficient
    if (into[v].size() > into[u].size()) {
      std::swap(u, v);
    }

    par[v] = u;
    ans -= edges[u][v] * size[v] + edges[v][u] * size[u];     // remove in between edges
    in[v] -= edges[u][v], in[u] -= edges[v][u];               // correct in[u/v] to exclude in between edges
    ans -= in[u] * size[u] + in[v] * 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 intersection that we'll also have to merge
    // add nodes on the path
    // step #1: u->node->v
    if (outof[u].size() < into[v].size()) {
      for (int i : outof[u]) {
        if (into[v].contains(i)) {
          additional.insert(root(root, i));
        }
      }
    } else {
      for (int i : into[v]) {
        if (outof[u].contains(i)) {
          additional.insert(root(root, i));
        }
      }
    }
    // step #2: v->node->u
    if (outof[v].size() < into[u].size()) {
      for (int i : outof[v]) {
        if (into[u].contains(i)) {
          additional.insert(root(root, i));
        }
      }
    } else {
      for (int i : into[u]) {
        if (outof[v].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]) {
        edges[u][a] += b;
      }
    } else {
      for (auto &[a, b] : edges[u]) {
        edges[v][a] += b;
      }
      std::swap(edges[u], edges[v]);
    }
    // part 2: edges[_][v] = edges[_][u]
    for (int i : into[v]) {
      edges[i][u] += edges[i][v];
      into[u].insert(i);
    }
    // part 3: outof[v] is now outof[u]
    if (outof[v].size() < outof[u].size()) {
      for (int i : outof[v]) {
        outof[u].insert(i);
      }
    } else {
      for (int i : outof[u]) {
        outof[v].insert(i);
      }
      std::swap(outof[u], outof[v]);
    }

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

    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 into[v].contains(u_orig)) {
      std::cout << ans << '\n';
      continue;
    }
    edges[u][v]++, in[v]++, into[v].insert(u_orig), outof[u].insert(v_orig);
    ans += size[v];
    if (edges[v][u]) {
      merge(merge, u, v);
    }
    std::cout << ans << '\n';
  }
}

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