Submission #1084032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084032		stefanneagu	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1041 ms	68780 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

int root[nmax], sz[nmax];
long long ans;

set<int> adj[nmax], inv[nmax], child[nmax];

int find(int a) {
  if(root[a] == a) {
    return a;
  }
  return root[a] = find(root[a]);
}

queue<pair<int, int>> q;

void weak(int a, int b) {
  adj[a].insert(b);
  inv[b].insert(a);
  if(adj[b].count(a)) {
    q.push({a, b});
  }
}

int ds_sz(int x) {
  return child[x].size() + adj[x].size() + inv[x].size();
}

void unite(int a, int b) {
  a = find(a), b = find(b);
  if(a == b) {
    return;
  }
  if(ds_sz(a) < ds_sz(b)) {
    swap(a, b);
  }
  ans += sz[b] * child[a].size() + sz[a] * child[b].size();
  root[b] = a;
  sz[a] += sz[b];
  for(auto it : child[b]) {
    if(child[a].count(it)) {
      ans -= sz[a];
    } else {
      child[a].insert(it);
    }
  }
  adj[a].erase(b), adj[b].erase(a);
  inv[a].erase(b), inv[b].erase(a);
  for(auto it : adj[b]) {
    inv[it].erase(b);
    weak(a, it);
  }
  for(auto it : inv[b]) {
    adj[it].erase(b);
    weak(it, a);
  }
}

int main() {
  cin.tie()->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    sz[i] = 1, root[i] = i;
    child[i].insert(i);
  }
  for(int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    b = find(b);
    if(find(a) != b && child[b].count(a) == 0) {
      ans += sz[b];
      child[b].insert(a);
      a = find(a);
      weak(a, b);
      while(!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        unite(p.first, p.second);
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

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