Submission #946396

#	Time	Username	Problem	Language	Result	Execution time	Memory
946396		rolandpetrean	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1054 ms	87304 KiB

joitter2

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

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;

const int N = 1e5 + 5;

int par[N], cnt[N];
set<int> in[N], out[N], inf[N];
set<pi> outf[N];

int ans = 0;
int get_cost(int u) {
  int cost = 0;
  // between
  cost += cnt[u] * (cnt[u] - 1);
  // coming in
  cost += (int)inf[u].size() * cnt[u];
  return cost;
}
int find(int u) {
  if (par[par[u]] != par[u]) par[u] = find(par[u]);
  return par[u];
}
void unite(int u, int v) {
  u = find(u); v = find(v);
  if (u == v) return;
  if (cnt[u] < cnt[v]) swap(u, v);
  
  in[u].erase(v);
  in[v].erase(u);
  out[u].erase(v);
  out[v].erase(u);
  for (int x : in[v]) {
    in[u].insert(x);
    out[x].erase(v);
    out[x].insert(u);
  }
  for (int x : out[v]) {
    out[u].insert(x);
    in[x].erase(v);
    in[x].insert(u);
  }
  for (auto x : outf[v]) {
    //cout << u << " " << v << " || " << x[0] << " " << x[1] << endl;
    if (find(x[0]) == u) {
      inf[u].erase(x[1]);
      continue;
    }
    outf[u].insert(x);
  }
  for (int x : inf[v]) {
    //cout << u << " " << v << " | " << x << endl;
    if (find(x) == u) {
      continue;
    }
    inf[u].insert(x);
  }
  
  cnt[u] += cnt[v];
  par[v] = u;
  for (int x : in[v]) {
    x = find(x);
    if (in[u].count(x) && out[u].count(x)) {
      ans -= get_cost(x);
      unite(u, x);
    }
  }
  for (int x : out[v]) {
    x = find(x);
    if (in[u].count(x) && out[u].count(x)) {
      ans -= get_cost(x);
      unite(u, x);
    }
  }
  in[v].clear();
  out[v].clear();
  inf[v].clear();
  cnt[v] = 0;

  /*cout << inf[u].size() << "!\n";
  for (int y : inf[u]) cout << y << " ";
  cout << endl << endl;*/
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, m;
  cin >> n >> m;
  
  for (int i = 1; i <= n; ++i) {
    par[i] = i;
    cnt[i] = 1;
  }
  
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    int fu = u, fv = v;
    u = find(u); v = find(v);
    if (u == v) {
      cout << ans << endl;
      continue;
    }
    
    ans -= get_cost(u) + get_cost(v);
    inf[v].insert(fu);
    outf[u].insert({fv, fu});
    out[u].insert(v);
    in[v].insert(u);
    if (in[u].count(v) && out[u].count(v)) unite(u, v);
    
    u = find(u); v = find(v);
    ans += get_cost(u);
    if (u != v) ans += get_cost(v);
    
    cout << ans << endl;
  }
}

/*
4 4
2 3
3 4
2 4
4 2
*/

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