제출 #1286984

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

joitter2

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

using ll = long long;

const int MAXN = 1e5 + 10;

int pai[MAXN]; ll sz[MAXN];

set<int> adj[MAXN], s[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);

  if(a == b) return;

  ans -= sz[a] * ((int) s[a].size()) + sz[a] * (sz[a] - 1);
  ans -= sz[b] * ((int) s[b].size()) + sz[b] * (sz[b] - 1);

  if(s[a].size() > s[b].size()) swap(a, b);

  for(auto x : s[a]) s[b].insert(x);

  pai[a] = b;
  sz[b] += sz[a];

  ans += sz[b] * ((int) s[b].size()) + sz[b] * (sz[b] - 1);

  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;
    sz[i] = 1;
  }

  while(m--){

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

    adj[a].insert(b);

    if(adj[b].count(a)){

      ans -= sz[get(a)];
      s[get(a)].erase(b);

      dsu_union(a, b);

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

      ans += sz[get(b)];
      s[get(b)].insert(a);

    }

    cout << ans << "\n";

  }

  return 0;
}

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