Submission #212010

#	Time	Username	Problem	Language	Result	Execution time	Memory
212010		EntityIT	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	1241 ms	87932 KiB

joitter2

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

struct Dsu {
  vector<int> pSet, nEle;
  LL nEdge;
  vector<map<int, set<int> > > edge;
  vector<set<int> > in, out;
  queue<pair<int, int> > q;
  Dsu(int nSet) {
    pSet.assign(nSet, 0); iota(all(pSet), 0);
    nEle.assign(nSet, 1);
    nEdge = 0;
    edge.assign(nSet, {});
    in.assign(nSet, {});
    out.assign(nSet, {});
  }

  int findSet(int i) { return i ^ pSet[i] ? pSet[i] = findSet(pSet[i]) : i; }
  void unite(int i, int j) {
    i = findSet(i); j = findSet(j);

    if (i == j) return ;

    if (nEle[i] > nEle[j]) swap(i, j);

    nEdge -= (LL)sz(edge[i][j]) * nEle[j]
             + (LL)sz(edge[j][i]) * nEle[i];
    for (const auto &k : edge[i][j]) {
      out[k].erase(j);
      in[j].erase(k);
    }
    edge[i].erase(j);
    for (const auto &k : edge[j][i]) {
      out[k].erase(i);
      in[i].erase(k);
    }
    edge[j].erase(i);
    nEdge += (LL)nEle[i] * nEle[j] * 2;

    nEdge -= (LL)sz(in[i]) * nEle[i] + (LL)sz(in[j]) * nEle[j];
    for (const auto &k : in[i]) {
      in[j].emplace(k);
      if (edge[j].find(findSet(k) ) != edge[j].end() ) q.emplace(j, k);
      out[k].erase(i); edge[findSet(k)][i].erase(k);
      out[k].emplace(j); edge[findSet(k)][j].emplace(k);
    }
    for (const auto &k : edge[i]) {
      for (const auto &t : k.second) {
        edge[j][k.first].emplace(t);
        if (edge[k.first].find(j) != edge[k.first].end() ) q.emplace(k.first, j);
      }
    }
    nEdge += (LL)sz(in[j]) * (nEle[i] + nEle[j]);

    pSet[i] = j;
    nEle[j] += nEle[i];
  }
  void doQ() {
    while (sz(q) ) {
      unite(q.front().first, q.front().second);
      q.pop();
    }
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, m; cin >> n >> m;

  Dsu dsu(n);
  while (m--) {
    int u, v; cin >> u >> v; --u; --v;
    int i = dsu.findSet(u), j = dsu.findSet(v);

    if (i ^ j && dsu.out[u].find(j) == dsu.out[u].end() ) {
      dsu.out[u].emplace(j); dsu.in[j].emplace(u);
      dsu.edge[i][j].emplace(u);
      dsu.nEdge += dsu.nEle[j];
      if (dsu.edge[j].find(i) != dsu.edge[j].end() ) {
        dsu.q.emplace(i, j);
        dsu.doQ();
      }
    }

//    for (int i = 0; i < n; ++i) {
//      cerr << i + 1 << " in " << dsu.findSet(i) + 1 << '\n';
//      if (i == dsu.findSet(i) ) {
//        for (const auto &j : dsu.in[i]) cerr << j + 1 << ' ';
//        cerr << '\n';
//        for (const auto &j : dsu.out[i]) cerr << j + 1 << ' ';
//        cerr << '\n';
//      }
//    }
//    cerr << "end\n";

    cout << dsu.nEdge << '\n';
  }

  return 0;
}

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