#include<bits/stdc++.h>
using namespace std;
using I=int;
using Lli=long long int;
const I N=100000;
set<pair<I,I>>viss;
set<I>unqs[N];
map<I,I>incs[N],outs[N];
I tots[N];
I pars[N];
Lli res=0;
I fnd(I i){
return pars[i]<0?i:pars[i]=fnd(pars[i]);
}
I siz(I i){
return-pars[fnd(i)];
}
void uni(I a,I b){
if((a=fnd(a))==(b=fnd(b)))return;
if(pars[a]>pars[b])swap(a,b);
Lli siz1=siz(a),siz2=siz(b);
res-=siz1*(siz1-1);
res-=siz2*(siz2-1);
res-=tots[a]*siz1;
res-=tots[b]*siz2;
for(auto c:unqs[b]){
unqs[a].insert(c);
}
for(auto[c,cnt]:incs[b]){
outs[c].erase(b);
tots[b]-=cnt;
if(c!=a){
outs[c][a]+=cnt;
incs[a][c]+=cnt;
tots[a]+=cnt;
}
}
for(auto[c,cnt]:outs[b]){
incs[c].erase(b);
tots[c]-=cnt;
if(c!=a){
incs[c][a]+=cnt;
outs[a][c]+=cnt;
tots[c]+=cnt;
}
}
unqs[b].clear();
incs[b].clear();
outs[b].clear();
pars[a]+=pars[b],pars[b]=a;
Lli siz3=siz(a);
res+=siz3*(siz3-1);
res+=tots[a]*siz3;
}
I main(){
cin.tie(0)->sync_with_stdio(0);
I n,m;cin>>n>>m;
fill_n(pars,n,-1);
for(I i=0;i<m;i++){
I a,b;cin>>a>>b,a--,b--;
I c=fnd(a),d=fnd(b);
if(!unqs[d].count(a)){
unqs[d].insert(a);
incs[d][c]++;
outs[c][d]++;
tots[d]++;
res+=siz(d);
}
viss.insert({a,b});
if(viss.count({b,a}))uni(a,b);
printf("%lli\n",res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
