Submission #329349

#	Time	Username	Problem	Language	Result	Execution time	Memory
329349		LifeHappen__	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	714 ms	44368 KiB

joitter2

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fi first
#define se second
#define mp make_pair

const int N = 1e5 + 5;
int n, m;
int lab[N], sz[N];
set<int> in[N];
set<ii> out[N];
int64_t ans;

int findset(int x) {
  if(lab[x] == x) return x;
  return lab[x] = findset(lab[x]);
}

void join(int u, int v) {
  int x = findset(u);
  int y = findset(v);
  if(x == y) return;
  auto it = out[y].lower_bound(make_pair(x, 0));
  if(it != out[y].end() && (*it).fi == x) {
    if(in[x].size() + out[x].size() < in[y].size() + out[y].size()) swap(x, y);
    vector<ii> vo;
    for (auto &i : out[y]) {
      ans -= sz[i.fi];
      in[i.fi].erase(i.se);
      if(i.fi != x) vo.push_back(i);
    }
    out[y].clear();
    ans += 1ll * sz[y] * (2 * sz[x] + in[x].size() - in[y].size());
    vector<int> vi;
    for (auto &i : in[y]) {
      int j = findset(i);
      out[j].erase(make_pair(y, i));
      if(j != x) vi.push_back(i);
    }
    in[y].clear();
    lab[y] = x;
    sz[x] += sz[y];
    for (int &i : vi) join(i, x);
    for (ii &i : vo) join(i.se, i.fi);
  } else if(!in[y].count(u)) {
    ans += 1ll * sz[y];
    in[y].insert(u);
    out[x].insert(make_pair(y, u));
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> n >> m;
  for (int i = 0; i < N; ++i)
    lab[i] = i, sz[i] = 1;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    join(u, v);
    cout << ans << '\n';
  }
}

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