제출 #1277259

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

joitter2

#include <bits/stdc++.h>

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::vector<int64_t> size(n, 1), in(n);
  std::vector<std::set<int>> adj(n), occ(n);
  std::iota(par.begin(), par.end(), 0);

  int64_t ans = 0;

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

  auto merge = [&](int u, int v) {
    u = root(root, u), v = root(root, v);
    if (u == v) {
      return;
    }
    if (occ[v].size() + adj[v].size() > occ[u].size() + adj[u].size()) {
      std::swap(u, v);
    }
    par[v] = u; // v is now the same node as u, move its adj list accordingly
    adj[u].erase(v), adj[v].erase(u);
    occ[v].erase(u), occ[u].erase(v);
    in[u]--, in[v]--, ans -= size[u] + size[v];
    for (int i : adj[v]) {
      adj[u].insert(i);
    }
    for (int i : occ[v]) {
      adj[i].erase(v);
      adj[i].insert(u);
      occ[u].insert(i);
    }
    occ[v].clear();
    adj[v].clear();
    ans -= in[u] * size[u] + size[u] * (size[u] - 1);
    ans -= in[v] * size[v] + size[v] * (size[v] - 1);
    size[u] += size[v];
    in[u] += in[v];
    ans += in[u] * size[u] + size[u] * (size[u] - 1);
    adj[u].insert(v), adj[v].insert(u);
    occ[v].insert(u), occ[u].insert(v);
  };

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

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