// 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 ¤t_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 ¤t_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;
^~~~~~
# |
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 |
# |
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 |
# |
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 |