Submission #1293624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293624		julia_08	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	10 ms	19008 KiB

joitter2

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

using ll = long long;

const int MAXN = 1e5 + 10;

int pai[MAXN];

set<int> in[MAXN], out[MAXN]; // components

set<int> vtx[MAXN]; // vertices that go into the component

set<int> comp[MAXN]; // component itself

queue<pair<int, int>> q;

ll ans;

int get_size(int a){
  return (int) (in[a].size() + out[a].size() + vtx[a].size() + comp[a].size());
}

ll get_ans(int a){

  ll sz = (ll) comp[a].size(), sz_out = (ll) vtx[a].size();
  return sz_out * sz + (sz * (sz - 1));

}

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

void dsu_union(int a, int b){

  if(a == b) return;

  int sz_a = get_size(a), sz_b = get_size(b);

  ans -= get_ans(a);
  ans -= get_ans(b);

  if(sz_a > sz_b) swap(a, b);

  for(auto x : comp[a]){

    comp[b].insert(a);
    if(vtx[b].count(x)) vtx[b].erase(x);

  }

  for(auto x : in[a]){

    x = get(x);

    if(!out[b].count(x)){

      in[b].insert(x);

    } else{
  
      out[b].erase(x);      
      q.push({x, b});

    }
  
  }

  for(auto x : vtx[a]){

    int rx = get(x);

    if(rx == b) continue;

    if(!out[b].count(rx)){
      vtx[b].insert(x);
    } else vtx[b].erase(x);

  }

  for(auto x : out[a]){

    x = get(x);

    if(!in[b].count(x)){
      
      out[b].insert(x);
    
    } else{

      in[b].erase(x);
      q.push({x, b});

    }

  }

  pai[a] = b;

  ans += get_ans(b);

}

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;

    int ra = get(a), rb = get(b);

    ans -= get_ans(rb);

    if(ra != rb){

      in[rb].insert(ra);
      out[ra].insert(rb);

      vtx[rb].insert(a);

      if(in[ra].count(rb)) q.push({ra, rb});

    }

    ans += get_ans(rb);

    while(!q.empty()){

      auto [a, b] = q.front();
      q.pop();
      
      dsu_union(a, b);
    
    }

    cout << ans << "\n";

  }

  return 0;
}

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