Submission #211899

#	Time	Username	Problem	Language	Result	Execution time	Memory
211899		mcdx9524	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++17	0 / 100	17 ms	23936 KiB

joitter2

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

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 7;

int par[N], sz[N], deg_sz[N], indeg[N];
set <int> comp[N];
set <int> g[N], kek[N];
set <int> gr[N], rg[N];
queue <pair <int, int> > upd;

ll ans = 0;

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

void unite(int a, int b) {
  a = get(a), b = get(b);
  if (a == b) {
    return;
  }
  if (deg_sz[a] < deg_sz[b]) {
    swap(a, b);
  }
  ans -= sz[a] * (ll) (sz[a] - 1);
  ans -= sz[b] * (ll) (sz[b] - 1);
  ans -= indeg[a] * (ll) sz[a];
  ans -= indeg[b] * (ll) sz[b];
  int cur = indeg[a] + indeg[b];
  set <int> rem;
  for (int v : comp[b]) {
    for (int to : gr[v]) {
      if (get(to) == a) {
        cur--;
        rem.insert(v);
        break;
      }
    }
    for (int to : rg[v]) {
      if (rem.count(to)) {
        continue;
      }
      if (get(to) == a) {
        cur--;
        rem.insert(to);
      } else {
        if (kek[to].count(a)) {
          cur--;
          rem.insert(to);
        }
      }
    }
  }
  indeg[a] = cur;
  for (int v : comp[b]) {
    comp[a].insert(v);
    for (int to : gr[v]) {
      if (g[get(to)].count(a) && a != get(to)) {
        upd.push({a, get(to)});
      }
    }
    for (int to : rg[v]) {
      g[get(to)].erase(b);
      g[get(to)].insert(a);
      kek[to].erase(get(b));
      kek[to].insert(a);
      if (g[a].count(get(to)) && a != get(to)) {
        upd.push({a, get(to)});
      }
    }
  }
  sz[a] += sz[b];
  deg_sz[a] += deg_sz[b];
  par[b] = a;
  ans += sz[a] * (ll) (sz[a] - 1);
  ans += indeg[a] * (ll) sz[a];
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    sz[i] = 1;
    par[i] = i;
    deg_sz[i] = 0;
    indeg[i] = 0;
    comp[i].insert(i);
  }
  for (int it = 0; it < m; it++) {
    int a, b;
    cin >> a >> b;
    gr[a].insert(b);
    rg[b].insert(a);
    deg_sz[get(a)]++;
    if (get(a) != get(b) && !kek[a].count(get(b))) {
      indeg[get(b)]++;
      ans += sz[get(b)];
    }
    kek[a].insert(get(b));
    a = get(a);
    b = get(b);
    g[a].insert(b);
    if (g[b].count(a)) {
      upd.push({a, b});
    }
    while (!upd.empty()) {
      int a = upd.back().first, b = upd.back().second;
      upd.pop();
      a = get(a), b = get(b);
      if (a == b) { 
        continue;
      }
      unite(a, b);
    }
    if (false && it == m - 1) {
      // << '$' << it << '\n';
      for (int i = 1; i <= n; i++) {
      //  cout << '#' << get(i) << ' ' << sz[get(i)] << ' ' << indeg[get(i)] << '\n';
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

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