#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5;
int n, m;
int lab[N];
set<int> s[N];
set<array<int, 2>> t[N];
vector<array<int, 2>> st;
int size(int u) {
return -lab[u];
}
int get(int u) {
return lab[u] < 0 ? u : lab[u] = get(lab[u]);
}
bool check(set<array<int, 2>> &st, int x) {
auto it = st.lower_bound(array<int, 2>{x});
return it != st.end() && (*it)[0] == x;
}
int count(set<array<int, 2>> &st, int x) {
auto it = st.lower_bound(array<int, 2>{x});
int cnt = 0;
for (; it != st.end() && (*it)[0] == x; it = st.erase(it)) {
++cnt;
}
return cnt;
}
long long res;
void mrg(int u, int v) {
u = get(u), v = get(v);
if (u == v) {
return;
}
int cnt = count(t[u], v);
res -= (long long) cnt * size(u);
cnt = count(t[v], u);
res -= (long long) cnt * size(v);
res += (long long) 2 * size(u) * size(v);
if (s[u].size() + t[u].size() < s[v].size() + t[v].size()) {
swap(u, v);
}
for (int x : s[v]) {
if (check(t[x], u)) {
st.push_back({x, u});
}
}
for (auto x : t[v]) {
if (s[u].find(x[0]) != s[u].end()) {
st.push_back({x[0], u});
}
}
for (int x : s[v]) {
s[u].insert(x);
auto it = t[x].lower_bound(array<int, 2>{v});
for (; it != t[x].end() && (*it)[0] == v; it = t[x].erase(it)) {
t[x].insert({u, (*it)[1]});
}
}
cnt = t[u].size();
for (auto [x, y] : t[v]) {
if (t[u].insert({x, y}).second) {
res += size(u);
} else {
--cnt;
}
s[x].erase(v);
s[x].insert(u);
}
res += (long long) cnt * size(v);
lab[u] += lab[v];
lab[v] = u;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
fill(lab + 1, lab + n + 1, -1);
for (int i = 1; i <= m; ++i) {
int a, b; cin >> a >> b;
int u = get(a), v = get(b);
if (u != v) {
s[u].insert(v);
res += t[v].insert({u, a}).second * size(v);
if (s[v].find(u) != s[v].end()) {
st.push_back({u, v});
}
while (st.size()) {
mrg(st.back()[0], st.back()[1]);
st.pop_back();
}
cout << res << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
9820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
