#include <iostream>
#include <vector>
#include <set>
typedef long long ll;
using namespace std;
// a, b, c sa bude pouzivat na vrcholy, x, y, z sa bude pouzivat na komponenty.
const int maxn = 1e5 + 5;
vector<int> p(maxn), siz(maxn, 1);
vector<set<int> > in(maxn); // hrany ktore idu do tohto komponentu
vector<set<pair<int, int> > > out(maxn); // hrany ktore idu z tohto komponentu, pamatame si aj ze z ktoreho vrchola idu
ll ans = 0;
int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
void merge(int a, int b)
{
int x = root(a), y = root(b);
if (x == y) return;
auto it = out[y].lower_bound({ x, -1 });
if (it != out[y].end() && it->first == x) // potrebujeme spojit x a y
{
// chceme mergnut x do y
if (out[x].size() + in[x].size() > out[y].size() + in[y].size()) swap(x, y);
vector<pair<int, int> > e;
for (const pair<int, int> &i : out[x]) // ideme sa pozriet na hrany ktore idu z x do inych vrcholov
{
int z = i.first, c = i.second; // (x(c)) -> (z)
ans -= siz[z];
in[z].erase(c);
if (z != y) e.push_back({ c, z }); // tuto hranu budeme musiet znovu skontrolovat a opravit
}
ans -= in[x].size() * 1ll * siz[x]; // tieto hrany budeme musiet prerobit, takze zatial zmazeme to co pridavaju
ans += in[y].size() * 1ll * siz[x]; // hrany ktore isli do y sa teraz mozu rozsirit aj do x
ans += siz[y] * 2ll * siz[x]; // tieto dva komponenty sa spoja, kazdy vrchol s kazdym
for (const int& c : in[x])
{
int z = root(c); // (z(c)) -> (x)
out[z].erase({ x, c });
if (z != y) e.push_back({ c, y });
}
in[x].clear(), out[x].clear();
p[x] = y, siz[y] += siz[x];
for (const pair<int, int>& i : e)
merge(i.first, i.second);
}
else if (!in[y].count(a))
{
in[y].insert(a), out[x].insert({ y, a });
ans += siz[y];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0, a, b; i < m; i++)
{
cin >> a >> b;
merge(a, b);
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10380 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 7 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10624 KB |
Output is correct |
| 9 |
Correct |
7 ms |
10520 KB |
Output is correct |
| 10 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 12 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 15 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 16 |
Correct |
6 ms |
10456 KB |
Output is correct |
| 17 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 18 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 19 |
Correct |
7 ms |
10572 KB |
Output is correct |
| 20 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 21 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 22 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 23 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 24 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 25 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 26 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 27 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 28 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 29 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 30 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 31 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 32 |
Correct |
6 ms |
10432 KB |
Output is correct |
| 33 |
Correct |
7 ms |
10444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10380 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 7 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10624 KB |
Output is correct |
| 9 |
Correct |
7 ms |
10520 KB |
Output is correct |
| 10 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 12 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 15 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 16 |
Correct |
6 ms |
10456 KB |
Output is correct |
| 17 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 18 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 19 |
Correct |
7 ms |
10572 KB |
Output is correct |
| 20 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 21 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 22 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 23 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 24 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 25 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 26 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 27 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 28 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 29 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 30 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 31 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 32 |
Correct |
6 ms |
10432 KB |
Output is correct |
| 33 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 34 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 35 |
Correct |
96 ms |
15940 KB |
Output is correct |
| 36 |
Correct |
143 ms |
17988 KB |
Output is correct |
| 37 |
Correct |
117 ms |
18084 KB |
Output is correct |
| 38 |
Correct |
115 ms |
17884 KB |
Output is correct |
| 39 |
Correct |
7 ms |
10572 KB |
Output is correct |
| 40 |
Correct |
8 ms |
10644 KB |
Output is correct |
| 41 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 42 |
Correct |
7 ms |
10480 KB |
Output is correct |
| 43 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 44 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 45 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 46 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 47 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 48 |
Correct |
9 ms |
10572 KB |
Output is correct |
| 49 |
Correct |
15 ms |
11212 KB |
Output is correct |
| 50 |
Correct |
118 ms |
18192 KB |
Output is correct |
| 51 |
Correct |
12 ms |
10828 KB |
Output is correct |
| 52 |
Correct |
123 ms |
16892 KB |
Output is correct |
| 53 |
Correct |
14 ms |
11156 KB |
Output is correct |
| 54 |
Correct |
112 ms |
17620 KB |
Output is correct |
| 55 |
Correct |
10 ms |
10940 KB |
Output is correct |
| 56 |
Correct |
10 ms |
10828 KB |
Output is correct |
| 57 |
Correct |
10 ms |
10956 KB |
Output is correct |
| 58 |
Correct |
12 ms |
10900 KB |
Output is correct |
| 59 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 60 |
Correct |
97 ms |
15508 KB |
Output is correct |
| 61 |
Correct |
9 ms |
10700 KB |
Output is correct |
| 62 |
Correct |
117 ms |
17832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 4 |
Correct |
6 ms |
10380 KB |
Output is correct |
| 5 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 7 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 8 |
Correct |
8 ms |
10624 KB |
Output is correct |
| 9 |
Correct |
7 ms |
10520 KB |
Output is correct |
| 10 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 12 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 15 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 16 |
Correct |
6 ms |
10456 KB |
Output is correct |
| 17 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 18 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 19 |
Correct |
7 ms |
10572 KB |
Output is correct |
| 20 |
Correct |
6 ms |
10500 KB |
Output is correct |
| 21 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 22 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 23 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 24 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 25 |
Correct |
6 ms |
10508 KB |
Output is correct |
| 26 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 27 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 28 |
Correct |
6 ms |
10504 KB |
Output is correct |
| 29 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 30 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 31 |
Correct |
6 ms |
10444 KB |
Output is correct |
| 32 |
Correct |
6 ms |
10432 KB |
Output is correct |
| 33 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 34 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 35 |
Correct |
96 ms |
15940 KB |
Output is correct |
| 36 |
Correct |
143 ms |
17988 KB |
Output is correct |
| 37 |
Correct |
117 ms |
18084 KB |
Output is correct |
| 38 |
Correct |
115 ms |
17884 KB |
Output is correct |
| 39 |
Correct |
7 ms |
10572 KB |
Output is correct |
| 40 |
Correct |
8 ms |
10644 KB |
Output is correct |
| 41 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 42 |
Correct |
7 ms |
10480 KB |
Output is correct |
| 43 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 44 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 45 |
Correct |
7 ms |
10444 KB |
Output is correct |
| 46 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 47 |
Correct |
8 ms |
10572 KB |
Output is correct |
| 48 |
Correct |
9 ms |
10572 KB |
Output is correct |
| 49 |
Correct |
15 ms |
11212 KB |
Output is correct |
| 50 |
Correct |
118 ms |
18192 KB |
Output is correct |
| 51 |
Correct |
12 ms |
10828 KB |
Output is correct |
| 52 |
Correct |
123 ms |
16892 KB |
Output is correct |
| 53 |
Correct |
14 ms |
11156 KB |
Output is correct |
| 54 |
Correct |
112 ms |
17620 KB |
Output is correct |
| 55 |
Correct |
10 ms |
10940 KB |
Output is correct |
| 56 |
Correct |
10 ms |
10828 KB |
Output is correct |
| 57 |
Correct |
10 ms |
10956 KB |
Output is correct |
| 58 |
Correct |
12 ms |
10900 KB |
Output is correct |
| 59 |
Correct |
8 ms |
10444 KB |
Output is correct |
| 60 |
Correct |
97 ms |
15508 KB |
Output is correct |
| 61 |
Correct |
9 ms |
10700 KB |
Output is correct |
| 62 |
Correct |
117 ms |
17832 KB |
Output is correct |
| 63 |
Correct |
404 ms |
44168 KB |
Output is correct |
| 64 |
Correct |
429 ms |
44144 KB |
Output is correct |
| 65 |
Correct |
380 ms |
44092 KB |
Output is correct |
| 66 |
Correct |
114 ms |
14904 KB |
Output is correct |
| 67 |
Correct |
159 ms |
18788 KB |
Output is correct |
| 68 |
Correct |
105 ms |
14924 KB |
Output is correct |
| 69 |
Correct |
219 ms |
19484 KB |
Output is correct |
| 70 |
Correct |
98 ms |
14868 KB |
Output is correct |
| 71 |
Correct |
115 ms |
14916 KB |
Output is correct |
| 72 |
Correct |
201 ms |
19040 KB |
Output is correct |
| 73 |
Correct |
207 ms |
18896 KB |
Output is correct |
| 74 |
Correct |
675 ms |
28272 KB |
Output is correct |
| 75 |
Correct |
378 ms |
24256 KB |
Output is correct |
| 76 |
Correct |
485 ms |
27156 KB |
Output is correct |
| 77 |
Correct |
604 ms |
27172 KB |
Output is correct |
| 78 |
Correct |
135 ms |
18372 KB |
Output is correct |
| 79 |
Correct |
247 ms |
21972 KB |
Output is correct |
| 80 |
Correct |
148 ms |
18296 KB |
Output is correct |
| 81 |
Correct |
240 ms |
21640 KB |
Output is correct |
| 82 |
Correct |
525 ms |
32884 KB |
Output is correct |
| 83 |
Correct |
463 ms |
32888 KB |
Output is correct |
| 84 |
Correct |
429 ms |
33220 KB |
Output is correct |
| 85 |
Correct |
378 ms |
33108 KB |
Output is correct |
| 86 |
Correct |
99 ms |
14024 KB |
Output is correct |
| 87 |
Correct |
135 ms |
16368 KB |
Output is correct |
| 88 |
Correct |
200 ms |
18984 KB |
Output is correct |
| 89 |
Correct |
495 ms |
26720 KB |
Output is correct |
