Submission #212021

#	Time	Username	Problem	Language	Result	Execution time	Memory
212021		rama_pang	Making Friends on Joitter is Fun (JOI20_joitter2)	C++14	100 / 100	943 ms	72184 KiB

joitter2

// Solution:
// Let a component denote a set of vertices such that each vertex has an outgoing edge to every
// other vertex in the component
//
// There are 2 cases when adding an edge:
//
// If we add an edge from a vertex v to a component c, then there will form an edge from v to 
// every node in component c.
//
// If we add an edge from a component a to a component b, and there exists an edge from b to a,
// then a and b will be merged into one component (a complete directed simple graph).
//
// We can maintain these edges and components using a set, merging them with the weighted union
// heuristic to achieve O(n log n) merges. If we use a map of sets, each merge takes O(log^2).
// This can be sped up using gp_hash_table of gp_hash_tables, speeding up each merge to O(1)
// amortized complexity.
//
// Time: O(n log n)
// Memory: O(n)

#include "bits/stdc++.h"
using namespace std;

const int MAXN = 100005;
const int MAXM = 300005;

int N, M;
int A[MAXM], B[MAXM];

long long Answer = 0;

void read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
  }
}

namespace disjoint_set { // maintain disjoint set of components
  int p[MAXN];
  int component_size[MAXN];

  void Init() {
    iota(p, p + MAXN, 0);
    fill(component_size, component_size + MAXN, 1);
  }

  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }

}

namespace ingoing_edges {
  map<int, set<int>> ingoing_edges_from_component[MAXN]; // set of ingoing edges from other components to component[] (a list oh them), thus number of edges = size() * component[].size()
  int total_size_ingoing_edges_from_component[MAXN]; // number of all element of elements of ingoing_edges_from_component[]

  void Insert(int base, int ingoing_component, int ingoing_id) {
    assert(ingoing_component == disjoint_set::Find(ingoing_id));
    if (ingoing_edges_from_component[base][ingoing_component].count(ingoing_id) == 0) {
      total_size_ingoing_edges_from_component[base]++;
      ingoing_edges_from_component[base][ingoing_component].emplace(ingoing_id);
    }
  }

  void Delete(int base, int ingoing_component, int ingoing_id) {
    assert(ingoing_component == disjoint_set::Find(ingoing_id));
    if (ingoing_edges_from_component[base][ingoing_component].count(ingoing_id) == 1) {
      total_size_ingoing_edges_from_component[base]--;
      ingoing_edges_from_component[base][ingoing_component].erase(ingoing_id);
    }
  }

  void Delete(int base, int ingoing_component) {
    total_size_ingoing_edges_from_component[base] -= ingoing_edges_from_component[base][ingoing_component].size();
    ingoing_edges_from_component[base].erase(ingoing_component);
  }

}

namespace outgoing_edges {
  map<int, int> edges_between_components[MAXN]; // count how many edges are there from component[] to another component divided by another component.size()
  int total_size_outgoing_edges_to_component[MAXN]; // sum of all edges_between_component[]'s value

  void Insert(int from, int to, int x) {
    total_size_outgoing_edges_to_component[from] += x;
    edges_between_components[from][to] += x;
  }

  void Delete(int from, int to, int x) {
    total_size_outgoing_edges_to_component[from] -= x;
    edges_between_components[from][to] -= x;
    if (edges_between_components[from][to] == 0) {
      edges_between_components[from].erase(to);
    }
  }

  void Delete(int from, int to) {
    total_size_outgoing_edges_to_component[from] -= edges_between_components[from][to];
    edges_between_components[from].erase(to);
  }

}

using ingoing_edges::ingoing_edges_from_component;
using ingoing_edges::total_size_ingoing_edges_from_component;

using outgoing_edges::edges_between_components;
using outgoing_edges::total_size_outgoing_edges_to_component;

bool IsThereAnEdgeBetweenComponent(int x, int y) {
  return (edges_between_components[x].count(y) == 1);
}

long long ComponentAnswer(int sz) { // count number of edges in one component (a component is a complete directed graph)
  return 1ll * sz * (sz - 1);
}

set<pair<int, int>> todo; // pending to use ConnectComponent(x, y)

void ConnectComponent(int x, int y) {
  x = disjoint_set::Find(x);
  y = disjoint_set::Find(y);
  if (x == y) return;


  int components_x_size = disjoint_set::component_size[x];
  int components_y_size = disjoint_set::component_size[y];


  { // delete edges between components to be connected
    Answer -= 1ll * edges_between_components[y][x] * components_x_size;
    Answer -= 1ll * edges_between_components[x][y] * components_y_size;
    
    outgoing_edges::Delete(x, y);
    outgoing_edges::Delete(y, x);
    
    ingoing_edges::Delete(x, y);
    ingoing_edges::Delete(y, x);
  }


  { // maintain weighted union heuristic and update disjoint set
    int total_size_x = total_size_ingoing_edges_from_component[x] + total_size_outgoing_edges_to_component[x];
    int total_size_y = total_size_ingoing_edges_from_component[y] + total_size_outgoing_edges_to_component[y];    
    
    if (total_size_x < total_size_y) {
      swap(x, y); // This still is affected by the weighted union heuristic, thus the will take O(n log n) merges total
      swap(components_x_size, components_y_size);
    }

    // Union in disjoint set
    disjoint_set::p[y] = x;
    disjoint_set::component_size[x] += disjoint_set::component_size[y];
    disjoint_set::component_size[y] = 0;
  }


  { // update answer for full component
    Answer -= ComponentAnswer(components_x_size);
    Answer -= ComponentAnswer(components_y_size);
    Answer += ComponentAnswer(components_x_size + components_y_size);
  }


  { // handle all merges of ingoing edge of x and y
    Answer += 1ll * total_size_ingoing_edges_from_component[x] * components_y_size;
    Answer += 1ll * total_size_ingoing_edges_from_component[y] * components_x_size;

    while (!ingoing_edges_from_component[y].empty()) {
      auto ingoing_edges_from_component_y_key_value_pair = begin(ingoing_edges_from_component[y]);
      int current_ingoing_component = ingoing_edges_from_component_y_key_value_pair->first;

      for (auto &current_ingoer : ingoing_edges_from_component_y_key_value_pair->second) {
        if (ingoing_edges_from_component[x][current_ingoing_component].count(current_ingoer) == 1) {
          outgoing_edges::Delete(current_ingoing_component, y, 1); // when merging edge_between_components[][x] and [][y], this will be double counted, so we subtract it
          Answer -= components_x_size + components_y_size; // Answer is also double counted
        } else {
          ingoing_edges::Insert(x, current_ingoing_component, current_ingoer);
        }
      }

      if (IsThereAnEdgeBetweenComponent(x, current_ingoing_component)) {
        todo.emplace(x, current_ingoing_component);
      }
      
      outgoing_edges::Insert(current_ingoing_component, x, edges_between_components[current_ingoing_component][y]);
      outgoing_edges::Delete(current_ingoing_component, y);
      ingoing_edges::Delete(y, current_ingoing_component);
    }
  }


  { // handle all merges of outgoing edge of x and y
    while (!edges_between_components[y].empty()) {
      auto outgoing_edges_y_key_value_pair = begin(edges_between_components[y]);
      int nxt_component = outgoing_edges_y_key_value_pair->first;

      for (auto &current_ingoer : ingoing_edges_from_component[nxt_component][y]) {  
        ingoing_edges::Insert(nxt_component, x, current_ingoer);
      }

      if (IsThereAnEdgeBetweenComponent(nxt_component, x)) {
        todo.emplace(x, nxt_component); // there is an edge from nxt_component to x and vice versa, so we need to merge them into one component
      }

      outgoing_edges::Insert(x, nxt_component, edges_between_components[y][nxt_component]);
      outgoing_edges::Delete(y, nxt_component);
      ingoing_edges::Delete(nxt_component, y);
    }
  }

}

void AddEdge(int x, int y) {
  int real_x = x;
  int real_y = y;

  x = disjoint_set::Find(x);
  y = disjoint_set::Find(y);
  if (x == y) return;

  if (IsThereAnEdgeBetweenComponent(y, x)) {
    todo.emplace(x, y);
    while (!todo.empty()) {
      int f, s;
      tie(f, s) = *begin(todo);
      todo.erase(make_pair(f, s));
      ConnectComponent(f, s);
    }
  } else {
    if (ingoing_edges_from_component[y][x].count(real_x) == 0) { // if edge doesn't exist already
      Answer += disjoint_set::component_size[y];

      outgoing_edges::Insert(x, y, 1);
      ingoing_edges::Insert(y, x, real_x);
    }
  }
}

void init() {
  disjoint_set::Init();
}

void solve() {
  for (int i = 0; i < M; i++) {
    AddEdge(A[i], B[i]);
    cout << Answer << "\n";
  } 
}

int main() {
  read();
  init();
  solve();
  return 0;
}

Compilation message (stderr)

joitter2.cpp: In function 'void AddEdge(int, int)':
joitter2.cpp:221:7: warning: unused variable 'real_y' [-Wunused-variable]
   int real_y = y;
       ^~~~~~

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