#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
struct DSU {
vector<int> par, sz;
int n;
inline void init(int _n) {
n = _n;
par.resize(n + 1), sz.resize(n + 1, 1);
}
int root(int x) {
return (par[x] == 0 ? x : par[x] = root(par[x]));
}
inline void join(int x, int y) {
x = root(x), y = root(y);
if(x != y) {
sz[y] += sz[x];
par[x] = y;
}
}
};
int main() {
#ifdef HOME
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
vector<map<int, int>> mpe(n + 1), mpc(n + 1);
map<pair<int, int>, vector<int>> ids;
vector<set<int>> in(n + 1);
// mpe[x][y] = x are muchie la comp. y
// mpc[x][y] = comp. x are muchie la comp. y
DSU dsu; dsu.init(n);
ll ans = 0;
while(m--) {
int x, y; cin >> x >> y;
int xx = dsu.root(x), yy = dsu.root(y);
if(xx != yy) {
if(mpc[yy][xx]) {
ans -= 1LL * dsu.sz[xx] * (dsu.sz[xx] - 1) + 1LL * dsu.sz[yy] * (dsu.sz[yy] - 1);
ans -= 1LL * mpc[yy][xx] * dsu.sz[xx];
ans += 1LL * (int)in[yy].size() * dsu.sz[xx];
for(auto id : ids[{yy, xx}]) {
in[xx].erase(id);
}
ids[{yy, xx}].clear();
ans += 1LL * (int)in[xx].size() * dsu.sz[yy];
if((int)in[xx].size() > (int)in[yy].size()) {
for(auto it : in[yy]) {
mpc[dsu.root(it)][yy]--;
if(mpe[it][xx] == 0) {
mpe[it][xx] = 1, mpc[dsu.root(it)][xx]++;
in[xx].insert(it);
ids[{dsu.root(it), xx}].push_back(it);
}
else {
ans -= dsu.sz[xx];
}
}
in[yy].clear();
dsu.join(yy, xx);
ans += 1LL * dsu.sz[xx] * (dsu.sz[xx] - 1);
}
else {
for(auto it : in[xx]) {
mpc[dsu.root(it)][xx]--;
if(mpe[it][yy] == 0) {
mpe[it][yy] = 1, mpc[dsu.root(it)][yy]++;
in[yy].insert(it);
ids[{dsu.root(it), yy}].push_back(it);
}
else {
ans -= dsu.sz[yy];
}
}
in[xx].clear();
dsu.join(xx, yy);
ans += 1LL * dsu.sz[yy] * (dsu.sz[yy] - 1);
}
}
else {
if(mpe[x][yy] == 0) {
mpe[x][yy] = 1, mpc[xx][yy]++;
ans += dsu.sz[yy];
in[yy].insert(x);
ids[{xx, yy}].push_back(x);
}
}
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
