#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n;
vector<int> f, siz;
DSU(int n) : n(n), f(n), siz(n, 1) { iota(f.begin(), f.end(), 0); };
int leader(int u) {
while (u != f[u]) {
u = f[u] = f[f[u]];
}
return u;
}
bool unionize(int u, int v) {
u = leader(u);
v = leader(v);
if (u == v) return false;
siz[v] += siz[u];
f[u] = v;
return true;
}
int size(int u) {
return siz[leader(u)];
}
bool same(int u, int v) {
return leader(u) == leader(v);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
long long res = 0;
DSU dsu(n);
vector<map<int, int>> out(n);
vector<map<int, int>> in(n);
vector<int> cnt_out(n, 0);
vector<int> cnt_in(n, 0);
auto addEdge = [&](auto self, int u, int v, int c) -> void {
if (dsu.same(u, v) || out[u].count(v)) return;
if (!out[v].count(u)) { // no v -> u, no need for merging
out[u][v] += c;
in[v][u] += c;
cnt_out[u] += c;
cnt_in[v] += c;
res += 1LL * c * dsu.size(v);
return;
}
// removes v -> u
res -= 1LL * dsu.size(u) * out[v][u];
cnt_out[v] -= out[v][u];
cnt_in[v] -= in[v][u];
cnt_out[u] -= out[u][v];
cnt_in[u] -= in[u][v];
out[v].erase(u);
in[u].erase(v); // this probably is the only place where something on u is erased
if (out[u].size() + in[u].size() > out[v].size() + in[v].size()) swap(u, v);
res += 2LL * dsu.size(u) * dsu.size(v);
res += 1LL * cnt_in[v] * dsu.size(u);
for (auto [w, c] : out[u]) { // removes u -> w
res -= 1LL * c * dsu.size(w);
cnt_in[w] -= in[w][u];
in[w].erase(u);
}
for (auto [w, c] : in[u]) { // removes w -> u
res -= 1LL * c * dsu.size(u);
cnt_out[w] -= out[w][u];
out[w].erase(u);
}
dsu.unionize(u, v);
// here u shouldn't be seen by any other node
for (auto [w, c] : out[u]) { // adds v -> w
self(self, w, v, c);
}
for (auto [w, c] : in[u]) { // adds w -> v
self(self, v, w, c);
}
};
while (m--) {
int u, v;
cin >> u >> v;
u--;
v--;
u = dsu.leader(u);
v = dsu.leader(v);
addEdge(addEdge, u, v, 1);
cout << res << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
