Submission #1045502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045502		abczz	Making Friends on Joitter is Fun (JOI20_joitter2)	C++17	100 / 100	1104 ms	106984 KiB

joitter2

#include <iostream>
#include <vector>
#include <map>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

vector <ll> V[100000];
queue <array<ll, 2>> Q;
map <ll, ll> adj[100000], radj[100000], cyc[100000], rcyc[100000];
ll n, m, a, b, f, P[100000], sz[100000];

ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}

void merge(ll a, ll b) {
  a = dsu(a), b = dsu(b);
  if (a == b) return;
  if (sz[a] < sz[b]) swap(a, b);
  for (auto [x, y] : cyc[b]) {
    if (x == a) continue;
    ++cyc[a][x];
    ++rcyc[x][a];
    if (cyc[x].count(a)) Q.push({x, a});
  }
  for (auto [x, y] : rcyc[b]) {
    if (x == a) continue;
    ++rcyc[a][x];
    ++cyc[x][a];
    if (cyc[a].count(x)) Q.push({x, a});
  }
  cyc[a].erase(b);
  rcyc[a].erase(b);
  cyc[b].clear();
  rcyc[b].clear();
  for (auto [x, y] : radj[b]) {
    if (dsu(x) == a || adj[x].count(a)) f -= sz[b];
    else {
      ++adj[x][a];
      ++radj[a][x];
      f += sz[a];
      f -= sz[b];
    }
    adj[x].erase(b);
  }
  radj[b].clear();
  for (auto u : V[b]) {
    if (adj[u].count(a)) {
      adj[u].erase(a);
      radj[a].erase(u);
      f -= sz[a];
    }
    V[a].push_back(u);
  }
  V[b].clear();
  f += radj[a].size() * sz[b];
  f += sz[a] * sz[b] * 2;
  sz[a] += sz[b];
  P[b] = a;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i=0; i<n; ++i) P[i] = i, sz[i] = 1, V[i].push_back(i);
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    if (dsu(a) == dsu(b)) {
      cout << f << '\n';
      continue;
    }
    b = dsu(b);
    if (!adj[a].count(b)) {
      ++adj[a][b];
      ++radj[b][a];
      f += sz[b];
    }
    a = dsu(a);
    ++cyc[a][b];
    ++rcyc[b][a];
    if (!cyc[b].count(a)) {
      cout << f << '\n';
      continue;
    }
    Q.push({a, b});
    while (!Q.empty()) {
      auto [x, y] = Q.front();
      Q.pop();
      merge(x, y);
    }
    cout << f << '\n';
  }
}

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