//besmellah
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
const int N = 3e5 + 5;
const long long INF = 1ll << 60;
int ans = 0;
namespace dsu {
int dpr[N];
set<array<int, 2>> in[N], out[N];
//sz[v] => sum of in[v].second
void init() {
memset(dpr, -1, sizeof dpr);
}
int gpr(int x) {
return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
}
bool ise(int v, int u) {//u <- v
auto it = in[u].lower_bound({v, -1});
return it != in[u].end() && (*it)[0] == v;
}
void merge(int u, int v) {
u = gpr(u), v = gpr(v);
if (u == v) return;
if (in[u].size() + out[u].size() > in[v].size() + out[v].size()) swap(u, v);
auto it = in[u].lower_bound({v, -1});
while (it != in[u].end() && (*it)[0] == v) {
ans -= -dpr[v];
out[v].erase({u, (*it)[1]});
in[u].erase(it);
it = in[u].lower_bound({v, -1});
}
it = in[v].lower_bound({u, -1});
while (it != in[v].end() && (*it)[0] == u) {
ans -= -dpr[u];
out[u].erase({v, (*it)[1]});
in[v].erase(it);
it = in[v].lower_bound({u, -1});
}
it = out[u].lower_bound({v, -1});
assert(it == out[u].end() || (*it)[0] != v);
it = out[v].lower_bound({u, -1});
assert(it == out[v].end() || (*it)[0] != u);
ans += dpr[u] * dpr[v] * 2ll;
vector<int> q;
int only_v = in[v].size();
for (auto [rt, x]: in[u]) only_v -= in[v].count({rt, x});
ans += -dpr[u] * only_v;
for (auto [rt, x]: in[u]) if (!in[v].count({rt, x}))
ans += -dpr[v];
for (auto [rt, x]: in[u]) {
in[v].insert({rt, x});
out[rt].erase({u, x});
out[rt].insert({v, x});
if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
}
for (auto [rt, x]: out[u]) {
out[v].insert({rt, x});
in[rt].erase({u, x});
in[rt].insert({v, x});
if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
}
in[u].clear(), out[u].clear();
dpr[v] += dpr[u];
dpr[u] = v;
for (auto x: q) merge(x, v);
}
void E(int u, int v) {
int tu = u;
u = gpr(u), v = gpr(v);
if (u == v || in[v].count({u, tu})) return;
in[v].insert({u, tu});
out[u].insert({v, tu});
ans += -dpr[v];
if (ise(u, v) && ise(v, u)) {
merge(u, v);
}
}
}
int n, m;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
dsu::init();
cin >> n >> m;
FOR(i, 0, m) {
int u, v;
cin >> u >> v;
--u, --v;
dsu::E(u, v);
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
30844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
30844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
30844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
