Submission #1277400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277400		avighna	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	0 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); // into[u] = the set of nodes coming into 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 = [&](int u, int v) {
    // make sure the later 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

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

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

  while (m--) {
    int u, v;
    std::cin >> u >> v;
    int u_orig = u - 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);
    ans += size[v];
    if (edges[v][u]) {
      merge(u, v);
    }
    std::cout << ans << '\n';
  }
}

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