#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
class UF {
public:
int N;
vector<int> e;
vector<set<int>> to;
vector<set<int>> c;
queue<pair<int, int>> to_merge;
ll res;
UF(int n) {
N = n;
e.resize(N, -1);
to.resize(N);
c.resize(N);
REP(i, N) c[i].insert(i);
res = 0;
}
int get(int a) {return e[a]<0?a:e[a] = get(e[a]);}
int sz(int a) {return -e[get(a)];}
int all_sz(int a) {return ssize(to[a])+ssize(c[a]);}
void addEdge(int a, int b) {
a = get(a); b = get(b);
to[a].insert(b);
if (to[b].count(a)) to_merge.push(mp(a, b));
}
void merge(int a, int b) {
// cerr << "MERGE: " << a << ' ' << b << '\n';
a = get(a); b = get(b);
if (a == b) return;
res += (ll)sz(a)*(ll)ssize(c[b])+(ll)sz(b)*(ll)ssize(c[a]);
if (all_sz(a) > all_sz(b)) swap(a, b);
for (int x : c[a]) {
if (c[b].count(x)) res -= sz(a)+sz(b);
else c[b].insert(x);
}
to[a].erase(b); to[b].erase(a);
for (int x : to[a]) {
if (to[b].count(x)) continue;
addEdge(b, x);
}
e[b] += e[a];
e[a] = b;
}
void add(int a, int b) {
b = get(b);
if (get(a) != b && !c[b].count(a)){
c[b].insert(a);
res += sz(b);
a = get(a);
addEdge(a, b);
while (to_merge.size() > 0) {
pair<int, int> p = to_merge.front();
to_merge.pop();
merge(p.fi, p.se);
}
}
}
};
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
UF u(n);
REP(i, m) {
int a, b;
cin >> a >> b;
a--; b--;
u.add(a, b);
cout << u.res << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
