Submission #217219

#	Time	Username	Problem	Language	Result	Execution time	Memory
217219		fedoseevtimofey	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	0 / 100	15 ms	19200 KiB

joitter2

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 1e5 + 7;
int sz[N];
int p[N];
set <int> out[N];
set <int> in[N];
set <int> who[N];
set <int> ver[N];

int get(int a) {
  return (a == p[a] ? a : p[a] = get(p[a]));
}

ll ans = 0;

void join(int a, int b) {
  a = get(a);
  b = get(b);
  if (a != b) {
    ans -= (ll)sz[a] * (sz[a] - 1);
    ans -= (ll)sz[b] * (sz[b] - 1);
    if (in[a].size() + out[a].size() + who[a].size() + ver[a].size() > in[b].size() + out[b].size() + who[b].size() + ver[b].size()) swap(a, b);
    in[a].erase(b);
    out[a].erase(b);
    in[b].erase(a);
    out[b].erase(a);
    ans += (ll)who[a].size() * sz[b];
    ans += (ll)who[b].size() * sz[a];
    for (int x : who[a]) {
      if (who[b].count(x)) {
        ans -= sz[a] + sz[b];
      } else if (ver[b].count(x)) {
        ans -= sz[a] + sz[b];
      } else {
        who[b].insert(x);
      }
    }
    for (int x : ver[a]) {
      if (who[b].count(x)) {
        ans -= sz[a] + sz[b];
        who[b].erase(x);
      }
      ver[b].insert(x);
    }
    vector <pair <int, int>> to_join;
    for (int x : in[a]) {
      if (out[b].count(x)) {
        to_join.push_back({x, b});
      }
      in[b].insert(x);
      out[x].erase(a);
      out[x].insert(b);
    }
    for (int x : out[a]) {
      if (in[b].count(x)) {
        to_join.push_back({x, b});
      }
      out[b].insert(x);
      in[x].erase(a);
      in[x].insert(b);
    }
    who[a] = {};
    ver[a] = {};
    in[a] = {};
    out[a] = {};

    p[a] = b;
    sz[b] += sz[a];
    ans += (ll)sz[b] * (sz[b] - 1);
    for (auto p : to_join) join(p.first, p.second);
  }
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    p[i] = i;
    sz[i] = 1;
    ver[i].insert(i);
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    int a = get(u);
    int b = get(v);
    if (a != b) {
      out[a].insert(b);
      in[b].insert(a);
    } 
    if (!who[b].count(u)) {
      who[b].insert(u);
      ans += sz[b];
    }
    if (out[b].count(a)) {
      join(a, b);
    }
    cout << ans << '\n';
  }
}

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