Submission #211861

# Submission time Handle Problem Language Result Execution time Memory
211861 2020-03-21T14:21:01 Z mcdx9524 Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
19 ms 23808 KB
#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];
vector <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];
  indeg[b] = 0;
  for (int v : comp[b]) {
    for (int to : gr[v]) {
      if (get(to) == a) {
        cur--;
      }
    }
    for (int to : rg[v]) {
      if (get(to) == a) {
        cur--;
      } else {
        if (g[get(to)].count(a)) {
          cur--;
        }
      }
    }
  }
  indeg[a] = cur;
  for (int v : comp[b]) {
    comp[a].insert(v);
    par[v] = a;
    for (int to : gr[v]) {
      if (g[get(to)].count(a)) {
        upd.push_back({a, get(to)});
      }
    }
    for (int to : rg[v]) {
      g[get(to)].erase(get(b));
      g[get(to)].insert(a);
    }
  }
  sz[a] += 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)]++;
    a = get(a);
    b = get(b);
    if (a != b && !g[a].count(b)) {
      indeg[b]++;
      ans += sz[b];
    }
    g[a].insert(b);
    if (g[b].count(a)) {
      upd.push_back({a, b});
    }
    while (!upd.empty()) {
      int a = upd.back().first, b = upd.back().second;
      upd.pop_back();
      if (a == b) { 
        continue;
      }
      unite(a, b);
    }
    cout << ans << '\n';
  }
  return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -