Submission #1286997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286997		julia_08	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	3 ms	4920 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> 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(s[a], s[b]);
    swap(sz[a], sz[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;

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

      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