#include <ios>
#include<iostream>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ull unsigned ll
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;
struct DSU{
vector<ll> p;
vector<multiset<ll>> in, out, mem;
queue<pair<ll, ll>> links;
ll pedge;
DSU(ll N){
p.resize(N+1, -1);
in.resize(N+1);
out.resize(N+1);
mem.resize(N+1);
for (ll i=1; i<=N; i++) mem[i].insert(i);
pedge=0;
}
ll get(ll x){
return p[x]==-1?x:p[x]=get(p[x]);
}
void unite(ll u, ll v){
if (in[u].size()+out[u].size()+mem[u].size()<in[v].size()+out[v].size()+mem[v].size()) swap(u, v);
// cout << "Unity: " << u << " " << v << ln;
// cout << "Pre: " << pedge << ln;
p[v]=u;
pedge+=mem[u].size()*mem[v].size()*2+in[u].size()*mem[v].size();
for (auto ind:in[v]){
pedge-=mem[v].size();
out[ind].erase(out[ind].find(v));
links.push({ind, u});
}
in[v].clear();
for (auto outd:out[v]){
pedge-=mem[outd].size();
in[outd].erase(in[outd].find(v));
links.push({outd, u});
}
out[v].clear();
for (auto child:mem[v]){
mem[u].insert(child);
}
mem[v].clear();
// cout << "Post: " << pedge << ln;
}
void follow(ll u, ll v){
links.push({u, v});
while (!links.empty()){
link(links.front().ff, links.front().ss);
links.pop();
}
// cout << "end\n";
}
void link(ll u, ll v){
// cout << "Linking: " << u << " - " << v << ln;
u=get(u);
v=get(v);
if (out[u].find(v)!=out[u].end()) return;
if (u==v) return;
if (out[v].find(u)!=out[v].end()){
pedge-=mem[u].size()*out[v].count(u);
out[v].erase(u);
in[u].erase(v);
unite(u, v);
return;
}else{
pedge+=mem[v].size();
out[u].insert(v);
in[v].insert(u);
}
}
};
void solve(){
ll n, m; cin >> n >> m;
DSU tr(n);
for (ll i=0; i<m; i++){
ll u, v; cin >> u >> v;
tr.follow(u, v);
cout << tr.pedge << ln;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
ll t=1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
