제출 #1287062

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

joitter2

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

using ll = long long;

const int MAXN = 1e5 + 10;

int pai[MAXN];

set<int> s[MAXN], comp[MAXN];

ll ans = 0;

int get(int v){
  if(v == pai[v]) return v;
  return pai[v] = get(pai[v]);
}

void dsu_union(int a, int b){

  a = get(a);
  b = get(b);

  ll sz_a = (ll) comp[a].size();
  ll sz_b = (ll) comp[b].size();

  ans -= sz_a * ((ll) s[a].size() + sz_a - 1);
  ans -= sz_b * ((ll) s[b].size() + sz_b - 1);

  if(sz_a + (int) s[a].size() > sz_b + (int) s[b].size()) swap(a, b);

  for(auto x : s[a]) if(!comp[b].count(x)) s[b].insert(x);

  for(auto x : comp[a]){
    comp[b].insert(x);
    if(s[b].count(x)) s[b].erase(x);
  }

  sz_b = (ll) comp[b].size();

  ans += sz_b * ((ll) s[b].size() + sz_b - 1);

  pai[a] = b;

  comp[a].clear();
  s[a].clear();

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  for(int i=1; i<=n; i++){
    pai[i] = i;
    comp[i] = {i};
  }

  while(m--){

    int a, b; cin >> a >> b;

    if(get(a) == get(b)){
      cout << ans << "\n";
      continue;
    }

    if(s[get(a)].count(b)){

      dsu_union(a, b);

    } else if(!s[get(b)].count(a)){

      ans += (int) comp[get(b)].size();
      s[get(b)].insert(a);

    }

    cout << ans << "\n";

  }

  return 0;
}

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