oj.uz

Submission #212022

# Submission time Handle Problem Language Result Execution time Memory
212022 2020-03-22T04:18:59 Z rama_pang Making Friends on Joitter is Fun (JOI20_joitter2) C++14
100 / 100
 1231 ms 204564 KB 
// 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 n).
// This can be sped up using 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;

#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;

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 {
  gp_hash_table<int, gp_hash_table<int, null_type>> 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].find(ingoing_id) == end(ingoing_edges_from_component[base][ingoing_component])) {
      total_size_ingoing_edges_from_component[base]++;
      ingoing_edges_from_component[base][ingoing_component].insert(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].find(ingoing_id) != end(ingoing_edges_from_component[base][ingoing_component])) {
      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 {
  gp_hash_table<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].find(y) != end(edges_between_components[x]));
}

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

struct chash {
  size_t operator()(const pair<int, int> &key) const {
    return (size_t) key.first * MAXN + key.second;
  }
};

gp_hash_table<pair<int, int>, null_type, chash> todo; // pending to use ConnectComponent(x, y) ((x, y) is hashed as x * N + 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].find(current_ingoer) != end(ingoing_edges_from_component[x][current_ingoing_component])) {
          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.insert({x, current_ingoing_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(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.insert({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.insert({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].find(real_x) == end(ingoing_edges_from_component[y][x])) { // 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

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 127992 KB Output is correct
2 Correct 105 ms 127992 KB Output is correct
3 Correct 105 ms 127992 KB Output is correct
4 Correct 107 ms 127992 KB Output is correct
5 Correct 102 ms 127992 KB Output is correct
6 Correct 101 ms 127992 KB Output is correct
7 Correct 105 ms 128056 KB Output is correct
8 Correct 108 ms 128080 KB Output is correct
9 Correct 105 ms 128196 KB Output is correct
10 Correct 103 ms 127992 KB Output is correct
11 Correct 102 ms 127992 KB Output is correct
12 Correct 107 ms 127992 KB Output is correct
13 Correct 108 ms 127992 KB Output is correct
14 Correct 103 ms 127992 KB Output is correct
15 Correct 103 ms 127992 KB Output is correct
16 Correct 104 ms 127992 KB Output is correct
17 Correct 101 ms 127996 KB Output is correct
18 Correct 104 ms 127992 KB Output is correct
19 Correct 102 ms 127992 KB Output is correct
20 Correct 103 ms 128052 KB Output is correct
21 Correct 107 ms 127992 KB Output is correct
22 Correct 116 ms 128120 KB Output is correct
23 Correct 106 ms 127992 KB Output is correct
24 Correct 104 ms 127992 KB Output is correct
25 Correct 102 ms 127992 KB Output is correct
26 Correct 104 ms 127992 KB Output is correct
27 Correct 106 ms 127992 KB Output is correct
28 Correct 105 ms 127992 KB Output is correct
29 Correct 108 ms 127992 KB Output is correct
30 Correct 102 ms 127992 KB Output is correct
31 Correct 114 ms 127992 KB Output is correct
32 Correct 102 ms 127924 KB Output is correct
33 Correct 105 ms 127996 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 127992 KB Output is correct
2 Correct 105 ms 127992 KB Output is correct
3 Correct 105 ms 127992 KB Output is correct
4 Correct 107 ms 127992 KB Output is correct
5 Correct 102 ms 127992 KB Output is correct
6 Correct 101 ms 127992 KB Output is correct
7 Correct 105 ms 128056 KB Output is correct
8 Correct 108 ms 128080 KB Output is correct
9 Correct 105 ms 128196 KB Output is correct
10 Correct 103 ms 127992 KB Output is correct
11 Correct 102 ms 127992 KB Output is correct
12 Correct 107 ms 127992 KB Output is correct
13 Correct 108 ms 127992 KB Output is correct
14 Correct 103 ms 127992 KB Output is correct
15 Correct 103 ms 127992 KB Output is correct
16 Correct 104 ms 127992 KB Output is correct
17 Correct 101 ms 127996 KB Output is correct
18 Correct 104 ms 127992 KB Output is correct
19 Correct 102 ms 127992 KB Output is correct
20 Correct 103 ms 128052 KB Output is correct
21 Correct 107 ms 127992 KB Output is correct
22 Correct 116 ms 128120 KB Output is correct
23 Correct 106 ms 127992 KB Output is correct
24 Correct 104 ms 127992 KB Output is correct
25 Correct 102 ms 127992 KB Output is correct
26 Correct 104 ms 127992 KB Output is correct
27 Correct 106 ms 127992 KB Output is correct
28 Correct 105 ms 127992 KB Output is correct
29 Correct 108 ms 127992 KB Output is correct
30 Correct 102 ms 127992 KB Output is correct
31 Correct 114 ms 127992 KB Output is correct
32 Correct 102 ms 127924 KB Output is correct
33 Correct 105 ms 127996 KB Output is correct
34 Correct 109 ms 128248 KB Output is correct
35 Correct 191 ms 136336 KB Output is correct
36 Correct 233 ms 140920 KB Output is correct
37 Correct 236 ms 142512 KB Output is correct
38 Correct 220 ms 141000 KB Output is correct
39 Correct 107 ms 127992 KB Output is correct
40 Correct 109 ms 128148 KB Output is correct
41 Correct 111 ms 128248 KB Output is correct
42 Correct 106 ms 127992 KB Output is correct
43 Correct 108 ms 128376 KB Output is correct
44 Correct 108 ms 128376 KB Output is correct
45 Correct 107 ms 127992 KB Output is correct
46 Correct 112 ms 127992 KB Output is correct
47 Correct 109 ms 128248 KB Output is correct
48 Correct 106 ms 128248 KB Output is correct
49 Correct 118 ms 130040 KB Output is correct
50 Correct 245 ms 141996 KB Output is correct
51 Correct 114 ms 128504 KB Output is correct
52 Correct 215 ms 137876 KB Output is correct
53 Correct 120 ms 129912 KB Output is correct
54 Correct 228 ms 140248 KB Output is correct
55 Correct 111 ms 128888 KB Output is correct
56 Correct 111 ms 129144 KB Output is correct
57 Correct 109 ms 128760 KB Output is correct
58 Correct 112 ms 128760 KB Output is correct
59 Correct 113 ms 128096 KB Output is correct
60 Correct 186 ms 132728 KB Output is correct
61 Correct 107 ms 128380 KB Output is correct
62 Correct 219 ms 140948 KB Output is correct

Subtask #3
83.0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 127992 KB Output is correct
2 Correct 105 ms 127992 KB Output is correct
3 Correct 105 ms 127992 KB Output is correct
4 Correct 107 ms 127992 KB Output is correct
5 Correct 102 ms 127992 KB Output is correct
6 Correct 101 ms 127992 KB Output is correct
7 Correct 105 ms 128056 KB Output is correct
8 Correct 108 ms 128080 KB Output is correct
9 Correct 105 ms 128196 KB Output is correct
10 Correct 103 ms 127992 KB Output is correct
11 Correct 102 ms 127992 KB Output is correct
12 Correct 107 ms 127992 KB Output is correct
13 Correct 108 ms 127992 KB Output is correct
14 Correct 103 ms 127992 KB Output is correct
15 Correct 103 ms 127992 KB Output is correct
16 Correct 104 ms 127992 KB Output is correct
17 Correct 101 ms 127996 KB Output is correct
18 Correct 104 ms 127992 KB Output is correct
19 Correct 102 ms 127992 KB Output is correct
20 Correct 103 ms 128052 KB Output is correct
21 Correct 107 ms 127992 KB Output is correct
22 Correct 116 ms 128120 KB Output is correct
23 Correct 106 ms 127992 KB Output is correct
24 Correct 104 ms 127992 KB Output is correct
25 Correct 102 ms 127992 KB Output is correct
26 Correct 104 ms 127992 KB Output is correct
27 Correct 106 ms 127992 KB Output is correct
28 Correct 105 ms 127992 KB Output is correct
29 Correct 108 ms 127992 KB Output is correct
30 Correct 102 ms 127992 KB Output is correct
31 Correct 114 ms 127992 KB Output is correct
32 Correct 102 ms 127924 KB Output is correct
33 Correct 105 ms 127996 KB Output is correct
34 Correct 109 ms 128248 KB Output is correct
35 Correct 191 ms 136336 KB Output is correct
36 Correct 233 ms 140920 KB Output is correct
37 Correct 236 ms 142512 KB Output is correct
38 Correct 220 ms 141000 KB Output is correct
39 Correct 107 ms 127992 KB Output is correct
40 Correct 109 ms 128148 KB Output is correct
41 Correct 111 ms 128248 KB Output is correct
42 Correct 106 ms 127992 KB Output is correct
43 Correct 108 ms 128376 KB Output is correct
44 Correct 108 ms 128376 KB Output is correct
45 Correct 107 ms 127992 KB Output is correct
46 Correct 112 ms 127992 KB Output is correct
47 Correct 109 ms 128248 KB Output is correct
48 Correct 106 ms 128248 KB Output is correct
49 Correct 118 ms 130040 KB Output is correct
50 Correct 245 ms 141996 KB Output is correct
51 Correct 114 ms 128504 KB Output is correct
52 Correct 215 ms 137876 KB Output is correct
53 Correct 120 ms 129912 KB Output is correct
54 Correct 228 ms 140248 KB Output is correct
55 Correct 111 ms 128888 KB Output is correct
56 Correct 111 ms 129144 KB Output is correct
57 Correct 109 ms 128760 KB Output is correct
58 Correct 112 ms 128760 KB Output is correct
59 Correct 113 ms 128096 KB Output is correct
60 Correct 186 ms 132728 KB Output is correct
61 Correct 107 ms 128380 KB Output is correct
62 Correct 219 ms 140948 KB Output is correct
63 Correct 812 ms 204564 KB Output is correct
64 Correct 768 ms 204540 KB Output is correct
65 Correct 781 ms 204396 KB Output is correct
66 Correct 339 ms 132472 KB Output is correct
67 Correct 526 ms 135672 KB Output is correct
68 Correct 307 ms 132472 KB Output is correct
69 Correct 446 ms 148736 KB Output is correct
70 Correct 326 ms 132476 KB Output is correct
71 Correct 325 ms 132472 KB Output is correct
72 Correct 548 ms 141188 KB Output is correct
73 Correct 540 ms 140928 KB Output is correct
74 Correct 1231 ms 189932 KB Output is correct
75 Correct 568 ms 152516 KB Output is correct
76 Correct 905 ms 168920 KB Output is correct
77 Correct 902 ms 169032 KB Output is correct
78 Correct 301 ms 137516 KB Output is correct
79 Correct 424 ms 140200 KB Output is correct
80 Correct 355 ms 157996 KB Output is correct
81 Correct 470 ms 162196 KB Output is correct
82 Correct 941 ms 175756 KB Output is correct
83 Correct 905 ms 175136 KB Output is correct
84 Correct 744 ms 168724 KB Output is correct
85 Correct 757 ms 168704 KB Output is correct
86 Correct 373 ms 131576 KB Output is correct
87 Correct 406 ms 133496 KB Output is correct
88 Correct 563 ms 142224 KB Output is correct
89 Correct 826 ms 164568 KB Output is correct