제출 #1265778

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

joitter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll ans;

template <int T> struct dsu {
  int sz[T], par[T];
  set<int> followers[T];
  int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
  void unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return;
    if (sz[x] > sz[y]) swap(x, y);
    ans += (ll)(sz[x]+sz[y])*(sz[x]+sz[y]-1) - (ll)sz[y]*(sz[y]-1) - (ll)sz[x]*(sz[x]-1);
    ans -= (ll)followers[x].size()*sz[x] + (ll)followers[y].size()*sz[y];
    par[x] = y;
    sz[y] += sz[x];
    if (followers[x].size() > followers[y].size()) followers[x].swap(followers[y]);
    followers[y].insert(followers[x].begin(), followers[x].end());
    vector<int> rm;
    for (auto e: followers[y]) if (find(e) == y) rm.push_back(e);
    for (auto e: rm) followers[y].erase(e);
    ans += followers[y].size()*sz[y];
  }
};

int n, m, u, v;
dsu<100001> graph;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  for (int i = 1; i < 100000; i++) graph.par[i] = i, graph.sz[i] = 1;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    if ((u = graph.find(u)) == (v = graph.find(v))) continue;
    if (graph.followers[u].count(v)) graph.unite(u, v);
    else if (!graph.followers[v].count(u)) {
      graph.followers[v].insert(u);
      ans += graph.sz[graph.find(v)];
    }
    cout << ans << '\n';
  }
}

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