#include <bits/stdc++.h>
using namespace std;
// 123
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<set<pair<int, int>>> g(n), rg(n);
vector<int> par(n, -1);
int64_t ans = 0;
queue<pair<int, int>> q;
function<int(int)> root = [&](int u) { return par[u] < 0 ? u : par[u] = root(par[u]); };
function<int(set<pair<int, int>>&, int)> cnt = [&](set<pair<int, int>>& s, int u) {
auto it = s.lower_bound(make_pair(u, -1));
int res = 0;
while (it != s.end() && it->first == u) {
res++, it = s.erase(it);
}
return res;
};
function<void(int, int)> check = [&](int u, int v) {
auto it = g[u].lower_bound(make_pair(v, -1));
if (it != g[u].end() && it->first == v) q.emplace(u, v);
};
function<void(int, int)> unite = [&](int u, int v) {
u = root(u), v = root(v);
if (u == v) return;
cnt(g[u], v), cnt(g[v], u);
ans += cnt(rg[v], u) * par[v];
ans += cnt(rg[u], v) * par[u];
ans += 2ll * par[u] * par[v];
ans -= 1ll * rg[v].size() * par[u];
ans -= 1ll * rg[u].size() * par[v];
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
if (g[u].size() < g[v].size()) g[u].swap(g[v]);
if (rg[u].size() < rg[v].size()) rg[u].swap(rg[v]);
for (auto x : rg[v]) {
if (rg[u].find(x) != rg[u].end()) ans += par[u] + par[v];
}
for (auto x : rg[v]) rg[u].emplace(x);
for (auto x : g[v]) g[u].emplace(x);
for (auto [x, y] : g[v]) {
auto it = rg[x].lower_bound(make_pair(v, -1));
while (it != rg[x].end() && it->first == v) {
rg[x].emplace(u, it->second);
it = rg[x].erase(it);
}
}
for (auto [x, y] : rg[v]) {
auto it = g[x].lower_bound(make_pair(v, -1));
while (it != g[x].end() && it->first == v) {
g[x].emplace(u, it->second);
it = g[x].erase(it);
}
}
for (auto [x, y] : g[v]) {
check(x, v);
}
for (auto [x, y] : rg[v]) {
check(v, x);
}
};
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
int a = root(u), b = root(v);
if (a != b) {
g[a].emplace(b, v);
ans -= rg[b].emplace(a, u).second * par[b];
check(b, a);
while (q.size()) {
auto [x, y] = q.front();
q.pop();
unite(x, y);
}
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
