Submission #1265799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265799		thewizardman	Making Friends on Joitter is Fun (JOI20_joitter2)	C++20	0 / 100	5 ms	10560 KiB

joitter2

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

ll ans;
int n, m, u, v, sz[100001], par[100001];
set<int> followers[100001], following[100001];
queue<pair<int, int>> q;

int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }

void merge(int x, int y) {
  for (auto e: following[x]) followers[e].erase(x), followers[e].insert(y);
  for (auto e: followers[x]) following[e].erase(x), following[e].insert(y);
  if (followers[x].size() > followers[y].size()) followers[x].swap(followers[y]);
  if (following[x].size() > following[y].size()) following[x].swap(following[y]);
  followers[y].insert(followers[x].begin(), followers[x].end());
  following[y].insert(following[x].begin(), following[x].end());
  vector<int> rm;
  for (auto e: followers[y]) if (find(e) == y) rm.push_back(e);
  for (auto e: rm) followers[y].erase(e), following[e].erase(y);
  for (auto e: followers[y]) if (following[y].count(e)) q.push({e, y});
}

void unite(int x, int y) {
  if ((x = find(x)) == (y = find(y))) return;
  if (sz[x] > sz[y]) swap(x, y);
  ans -= (ll)sz[x]*(sz[x]-1) + (ll)sz[y]*(sz[y]-1);
  ans -= (ll)followers[x].size()*sz[x] + (ll)followers[y].size()*sz[y];
  par[x] = y;
  sz[y] += sz[x];
  merge(x, y);
  ans += (ll)sz[y]*(sz[y]-1);
  ans += (ll)followers[y].size()*sz[y];
}

void add(int u, int v) {
  if (followers[find(u)].count(find(v))) q.push({u, v});
  else if (!followers[find(v)].count(find(u))) {
    followers[find(v)].insert(find(u));
    following[find(u)].insert(find(v));
    ans += sz[find(v)];
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  for (int i = 1; i < 100001; i++) par[i] = i, sz[i] = 1;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    add(u, v);
    while (!q.empty()) unite(q.front().first, q.front().second), q.pop();
    cout << ans << '\n';
  }
}

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