#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll get(int l, int r = -1) {
if (r == -1) return 1ll * l * (l + 1) / 2;
return 1ll * (r - l + 1) * (l + r) / 2;
}
void solve() {
int n, m;
cin >> n >> m;
ll ans = 0;
vector<vector<int>> have(n + 1);
vector<set<int>> in(n + 1), out(n + 1);
set<pair<int, int>> all, adj;
vector<int> weight(n + 1, 2), par(n + 1);
for (int i = 1; i <= n; i++) have[i].emplace_back(i);
iota(par.begin(), par.end(), 0);
while (m--) {
int u, v;
cin >> u >> v;
if (par[u] == par[v] or all.count(make_pair(u, par[v]))) {
cout << ans << '\n';
continue;
}
if (adj.count(make_pair(par[v], par[u]))) {
u = par[u], v = par[v];
adj.erase(make_pair(v, u));
if (weight[u] < weight[v]) swap(u, v);
ans -= 1ll * have[u].size() * (have[u].size() - 1);
ans -= 1ll * have[v].size() * (have[v].size() - 1);
for (int x: in[u]) {
ans -= have[u].size();
}
weight[u] -= have[u].size() + in[u].size();
// cout << u << ' ' << v << endl;
for (int x: in[v]) {
ans -= have[v].size();
if (par[x] == u) continue;
in[u].insert(x);
out[x].erase(v);
out[x].insert(u);
if (adj.count(make_pair(par[x], v))) adj.erase(make_pair(par[x], v));
adj.emplace(par[x], u);
all.erase(make_pair(x, v));
all.emplace(x, u);
}
int old = have[u].size();
for (int x: have[v]) {
par[x] = u;
have[u].emplace_back(x);
for (int y: out[x]) if (y == u) {
in[u].erase(x);
}
weight[u] += out[x].size();
}
weight[u] += have[u].size() + in[u].size();
// cout << '\t';
// for (int x: in[u]) cout << x << ' ';
// cout << endl;
for (int x: in[u]) ans += have[u].size();
ans += have[u].size() * (have[u].size() - 1);
in[v].clear(), have[v].clear();
} else {
ans += have[par[v]].size();
out[u].insert(par[v]);
in[par[v]].insert(u);
weight[par[u]]++, weight[par[v]]++;
adj.emplace(par[u], par[v]);
all.emplace(u, par[v]);
}
cout << ans << '\n';
}
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int queries = 1;
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// cin >> queries;
for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
cout << "Test case: " << test_case << endl;
#endif
solve();
cout << '\n';
}
}
Compilation message
joitter2.cpp: In function 'void solve()':
joitter2.cpp:33:22: warning: unused variable 'x' [-Wunused-variable]
33 | for (int x: in[u]) {
| ^
joitter2.cpp:66:22: warning: unused variable 'x' [-Wunused-variable]
66 | for (int x: in[u]) ans += have[u].size();
| ^
joitter2.cpp:53:17: warning: unused variable 'old' [-Wunused-variable]
53 | int old = have[u].size();
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
500 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
500 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
500 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
